Skip to main content

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

  1. The function countSetUnsetBit(num) takes an integer num as input.
  2. It checks if the given number is negative (num < 0). If it is, the function returns without processing.
  3. The function prints the given number.
  4. It initializes two counters: activeBit for counting active bits (set to 1) and inActiveBit for counting inactive bits (set to 0).
  5. The function enters a loop that continues until the number becomes 0.
  6. 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.
  7. 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, the inActiveBit counter is incremented.
  8. The number is right-shifted by one position (num = num >> 1) to process the next bit in the next iteration.
  9. After the loop completes, the counters activeBit and inActiveBit will contain the respective counts of active and inactive bits.
  10. 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:

  1. 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".

  2. 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".

  3. 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".

  4. 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".

  5. 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.

Last updated on by Kalkicode




Comment

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