Count the number of active and inactive bits of a number
The problem we're addressing is to count the number of active (set) and inactive (unset) bits in the binary representation of a given number. We want to determine how many bits are set to 1 and how many are set to 0 in the binary form of the number. This problem involves bitwise operations to analyze the individual bits of the number.
Problem Statement and Description
Given an integer num
, the task is to count the number of active (set) and inactive (unset) bits in its
binary representation. We need to perform bitwise operations to examine each bit of the number and count how many of
them are set to 1 and how many are set to 0.
Example
Consider the number 17. In binary form, it is represented as 10001. This number contains 2 active bits (set to 1) and 3 inactive bits (set to 0). Therefore, the expected output for this example should be:
- Active Bits: 2
- Inactive Bits: 3
Idea to Solve the Problem
The primary idea to solve this problem is to use bitwise operations to iterate through the bits of the given number. We'll use the bitwise AND operation to check whether a specific bit is set to 1 or not. Based on the result, we'll update the counters for active and inactive bits.
Pseudocode
Here's the pseudocode for the algorithm:
function countSetUnsetBit(num):
if num < 0:
return
print "Number: ", num
activeBit = 0
inActiveBit = 0
while num > 0:
if num & 1 == 1:
activeBit += 1
else:
inActiveBit += 1
num = num >> 1
print "Active Bits: ", activeBit
print "Inactive Bits: ", inActiveBit
Algorithm Explanation
- The function
countSetUnsetBit(num)
takes an integernum
as input. - It checks if the given number is negative (
num < 0
). If it is, the function returns without processing. - The function prints the given number.
- It initializes two counters:
activeBit
for counting active bits (set to 1) andinActiveBit
for counting inactive bits (set to 0). - The function enters a loop that continues until the number becomes 0.
- In each iteration of the loop, it uses the bitwise AND operation
(num & 1)
to check whether the least significant bit of the number is set to 1. - If the result of the AND operation is 1, it means the bit is active (set to 1), and the
activeBit
counter is incremented. Otherwise, theinActiveBit
counter is incremented. - The number is right-shifted by one position (
num = num >> 1
) to process the next bit in the next iteration. - After the loop completes, the counters
activeBit
andinActiveBit
will contain the respective counts of active and inactive bits. - The function prints the results.
Code Solution
// C Program
// Count the number of active and inactive bits of a number
#include <stdio.h>
// Count the number of set and unset bits of a number
void countSetUnsetBit(int num)
{
if(num < 0)
{
return;
}
// Display given number
printf("\n Number : %d",num);
int activeBit = 0;
int inActiveBit = 0;
while(num > 0)
{
if(num & 1==1)
{
activeBit++;
}
else
{
inActiveBit++;
}
num = num >> 1;
}
// Display calculated result
printf("\n Active Bits : %d",activeBit);
printf("\n Inactive Bits : %d\n",inActiveBit);
}
int main(int argc, char const *argv[])
{
// Test Cases
// 17 (10001)
countSetUnsetBit(17);
// 34 (100010)
countSetUnsetBit(34);
// 1 (1)
countSetUnsetBit(1);
// 7 (111)
countSetUnsetBit(7);
// 21 (10101)
countSetUnsetBit(21);
return 0;
}
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
/*
Java Program
Count the number of active and inactive bits of a number
*/
public class BitCounting
{
// Count the number of set and unset bits of a number
public void countSetUnsetBit(int num)
{
if (num < 0)
{
return;
}
// Display given number
System.out.print("\n Number : " + num );
int activeBit = 0;
int inActiveBit = 0;
while (num > 0)
{
if ((num & 1) == 1)
{
activeBit++;
}
else
{
inActiveBit++;
}
num = num >> 1;
}
// Display calculated result
System.out.print("\n Active Bits : " + activeBit );
System.out.print("\n Inactive Bits : " + inActiveBit + "\n");
}
public static void main(String[] args)
{
BitCounting task = new BitCounting();
// Test Cases
// 17 (10001)
task.countSetUnsetBit(17);
// 34 (100010)
task.countSetUnsetBit(34);
// 1 (1)
task.countSetUnsetBit(1);
// 7 (111)
task.countSetUnsetBit(7);
// 21 (10101)
task.countSetUnsetBit(21);
}
}
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Count the number of active and inactive bits of a number
*/
class BitCounting
{
public:
// Count the number of set and unset bits of a number
void countSetUnsetBit(int num)
{
if (num < 0)
{
return;
}
// Display given number
cout << "\n Number : " << num;
int activeBit = 0;
int inActiveBit = 0;
while (num > 0)
{
if ((num &1) == 1)
{
activeBit++;
}
else
{
inActiveBit++;
}
num = num >> 1;
}
// Display calculated result
cout << "\n Active Bits : " << activeBit;
cout << "\n Inactive Bits : " << inActiveBit << "\n";
}
};
int main()
{
BitCounting task = BitCounting();
// Test Cases
// 17 (10001)
task.countSetUnsetBit(17);
// 34 (100010)
task.countSetUnsetBit(34);
// 1 (1)
task.countSetUnsetBit(1);
// 7 (111)
task.countSetUnsetBit(7);
// 21 (10101)
task.countSetUnsetBit(21);
return 0;
}
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
// Include namespace system
using System;
/*
C# Program
Count the number of active and inactive bits of a number
*/
public class BitCounting
{
// Count the number of set and unset bits of a number
public void countSetUnsetBit(int num)
{
if (num < 0)
{
return;
}
// Display given number
Console.Write("\n Number : " + num);
int activeBit = 0;
int inActiveBit = 0;
while (num > 0)
{
if ((num & 1) == 1)
{
activeBit++;
}
else
{
inActiveBit++;
}
num = num >> 1;
}
// Display calculated result
Console.Write("\n Active Bits : " + activeBit);
Console.Write("\n Inactive Bits : " + inActiveBit + "\n");
}
public static void Main(String[] args)
{
BitCounting task = new BitCounting();
// Test Cases
// 17 (10001)
task.countSetUnsetBit(17);
// 34 (100010)
task.countSetUnsetBit(34);
// 1 (1)
task.countSetUnsetBit(1);
// 7 (111)
task.countSetUnsetBit(7);
// 21 (10101)
task.countSetUnsetBit(21);
}
}
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
<?php
/*
Php Program
Count the number of active and inactive bits of a number
*/
class BitCounting
{
// Count the number of set and unset bits of a number
public function countSetUnsetBit($num)
{
if ($num < 0)
{
return;
}
// Display given number
echo "\n Number : ". $num;
$activeBit = 0;
$inActiveBit = 0;
while ($num > 0)
{
if (($num & 1) == 1)
{
$activeBit++;
}
else
{
$inActiveBit++;
}
$num = $num >> 1;
}
// Display calculated result
echo "\n Active Bits : ". $activeBit;
echo "\n Inactive Bits : ". $inActiveBit ."\n";
}
}
function main()
{
$task = new BitCounting();
// Test Cases
// 17 (10001)
$task->countSetUnsetBit(17);
// 34 (100010)
$task->countSetUnsetBit(34);
// 1 (1)
$task->countSetUnsetBit(1);
// 7 (111)
$task->countSetUnsetBit(7);
// 21 (10101)
$task->countSetUnsetBit(21);
}
main();
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
/*
Node Js Program
Count the number of active and inactive bits of a number
*/
class BitCounting
{
// Count the number of set and unset bits of a number
countSetUnsetBit(num)
{
if (num < 0)
{
return;
}
// Display given number
process.stdout.write("\n Number : " + num);
var activeBit = 0;
var inActiveBit = 0;
while (num > 0)
{
if ((num & 1) == 1)
{
activeBit++;
}
else
{
inActiveBit++;
}
num = num >> 1;
}
// Display calculated result
process.stdout.write("\n Active Bits : " + activeBit);
process.stdout.write("\n Inactive Bits : " + inActiveBit + "\n");
}
}
function main()
{
var task = new BitCounting();
// Test Cases
// 17 (10001)
task.countSetUnsetBit(17);
// 34 (100010)
task.countSetUnsetBit(34);
// 1 (1)
task.countSetUnsetBit(1);
// 7 (111)
task.countSetUnsetBit(7);
// 21 (10101)
task.countSetUnsetBit(21);
}
main();
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
# Python 3 Program
# Count the number of active and inactive bits of a number
class BitCounting :
# Count the number of set and unset bits of a number
def countSetUnsetBit(self, num) :
if (num < 0) :
return
# Display given number
print("\n Number : ", num, end = "")
activeBit = 0
inActiveBit = 0
while (num > 0) :
if ((num & 1) == 1) :
activeBit += 1
else :
inActiveBit += 1
num = num >> 1
# Display calculated result
print("\n Active Bits : ", activeBit, end = "")
print("\n Inactive Bits : ", inActiveBit )
def main() :
task = BitCounting()
# Test Cases
# 17 (10001)
task.countSetUnsetBit(17)
# 34 (100010)
task.countSetUnsetBit(34)
# 1 (1)
task.countSetUnsetBit(1)
# 7 (111)
task.countSetUnsetBit(7)
# 21 (10101)
task.countSetUnsetBit(21)
if __name__ == "__main__": main()
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
# Ruby Program
# Count the number of active and inactive bits of a number
class BitCounting
# Count the number of set and unset bits of a number
def countSetUnsetBit(num)
if (num < 0)
return
end
# Display given number
print("\n Number : ", num)
activeBit = 0
inActiveBit = 0
while (num > 0)
if ((num & 1) == 1)
activeBit += 1
else
inActiveBit += 1
end
num = num >> 1
end
# Display calculated result
print("\n Active Bits : ", activeBit)
print("\n Inactive Bits : ", inActiveBit ,"\n")
end
end
def main()
task = BitCounting.new()
# Test Cases
# 17 (10001)
task.countSetUnsetBit(17)
# 34 (100010)
task.countSetUnsetBit(34)
# 1 (1)
task.countSetUnsetBit(1)
# 7 (111)
task.countSetUnsetBit(7)
# 21 (10101)
task.countSetUnsetBit(21)
end
main()
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
/*
Scala Program
Count the number of active and inactive bits of a number
*/
class BitCounting
{
// Count the number of set and unset bits of a number
def countSetUnsetBit(n: Int): Unit = {
var num = n;
if (num < 0)
{
return;
}
// Display given number
print("\n Number : " + num);
var activeBit: Int = 0;
var inActiveBit: Int = 0;
while (num > 0)
{
if ((num & 1) == 1)
{
activeBit += 1;
}
else
{
inActiveBit += 1;
}
num = num >> 1;
}
// Display calculated result
print("\n Active Bits : " + activeBit);
print("\n Inactive Bits : " + inActiveBit + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BitCounting = new BitCounting();
// Test Cases
// 17 (10001)
task.countSetUnsetBit(17);
// 34 (100010)
task.countSetUnsetBit(34);
// 1 (1)
task.countSetUnsetBit(1);
// 7 (111)
task.countSetUnsetBit(7);
// 21 (10101)
task.countSetUnsetBit(21);
}
}
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
/*
Swift 4 Program
Count the number of active and inactive bits of a number
*/
class BitCounting
{
// Count the number of set and unset bits of a number
func countSetUnsetBit(_ n: Int)
{
var num = n;
if (num < 0)
{
return;
}
// Display given number
print("\n Number : ", num, terminator: "");
var activeBit: Int = 0;
var inActiveBit: Int = 0;
while (num > 0)
{
if ((num & 1) == 1)
{
activeBit += 1;
}
else
{
inActiveBit += 1;
}
num = num >> 1;
}
// Display calculated result
print("\n Active Bits : ", activeBit, terminator: "");
print("\n Inactive Bits : ", inActiveBit );
}
}
func main()
{
let task: BitCounting = BitCounting();
// Test Cases
// 17 (10001)
task.countSetUnsetBit(17);
// 34 (100010)
task.countSetUnsetBit(34);
// 1 (1)
task.countSetUnsetBit(1);
// 7 (111)
task.countSetUnsetBit(7);
// 21 (10101)
task.countSetUnsetBit(21);
}
main();
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
/*
Kotlin Program
Count the number of active and inactive bits of a number
*/
class BitCounting
{
// Count the number of set and unset bits of a number
fun countSetUnsetBit(n: Int): Unit
{
var num = n;
if (num < 0)
{
return;
}
// Display given number
print("\n Number : " + num);
var activeBit: Int = 0;
var inActiveBit: Int = 0;
while (num > 0)
{
if ((num and 1) == 1)
{
activeBit += 1;
}
else
{
inActiveBit += 1;
}
num = num shr 1;
}
// Display calculated result
print("\n Active Bits : " + activeBit);
print("\n Inactive Bits : " + inActiveBit + "\n");
}
}
fun main(args: Array <String> ): Unit
{
var task: BitCounting = BitCounting();
// Test Cases
// 17 (10001)
task.countSetUnsetBit(17);
// 34 (100010)
task.countSetUnsetBit(34);
// 1 (1)
task.countSetUnsetBit(1);
// 7 (111)
task.countSetUnsetBit(7);
// 21 (10101)
task.countSetUnsetBit(21);
}
Output
Number : 17
Active Bits : 2
Inactive Bits : 3
Number : 34
Active Bits : 2
Inactive Bits : 4
Number : 1
Active Bits : 1
Inactive Bits : 0
Number : 7
Active Bits : 3
Inactive Bits : 0
Number : 21
Active Bits : 3
Inactive Bits : 2
Resultant Output Explanation
For the given code and the provided test cases, let's break down the output:
-
For the number 17:
- Binary representation: 10001
- Active bits: 2 (bit positions 0 and 4)
- Inactive bits: 3 (bit positions 1, 2, and 3)
- The output is "Number: 17\nActive Bits: 2\nInactive Bits: 3".
-
For the number 34:
- Binary representation: 100010
- Active bits: 2 (bit positions 1 and 5)
- Inactive bits: 4 (bit positions 0, 2, 3, and 4)
- The output is "Number: 34\nActive Bits: 2\nInactive Bits: 4".
-
For the number 1:
- Binary representation: 1
- Active bits: 1 (bit position 0)
- Inactive bits: 0
- The output is "Number: 1\nActive Bits: 1\nInactive Bits: 0".
-
For the number 7:
- Binary representation: 111
- Active bits: 3 (bit positions 0, 1, and 2)
- Inactive bits: 0
- The output is "Number: 7\nActive Bits: 3\nInactive Bits: 0".
-
For the number 21:
- Binary representation: 10101
- Active bits: 3 (bit positions 0, 2, and 4)
- Inactive bits: 2 (bit positions 1 and 3)
- The output is "Number: 21\nActive Bits: 3\nInactive Bits: 2".
Time Complexity
The time complexity of this algorithm is proportional to the number of bits in the binary representation of the
input number. In the worst case, where all bits of the number are considered, the time complexity is O(log n), where
n
is the value of the input number.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment