Check if a number has same number of set and unset bits

The problem we're addressing is to determine whether a given integer has the same number of active (set) and inactive (unset) bits in its binary representation. In other words, we want to check if the count of 1s and 0s in the binary form of the number is equal. 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 check whether it has the same number of active (set) and inactive (unset) bits in its binary representation. We need to perform bitwise operations to iterate through the bits of the number and keep track of the counts of active and inactive bits.

Example

Consider the number 9. In binary form, it is represented as 1001. This number contains 2 active bits (set to 1) and 2 inactive bits (set to 0), resulting in an equal count of both types of bits. Therefore, the expected output for this example should be "Equal set and unset bits".

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 a counter that represents the difference between the count of active and inactive bits. If this counter is zero at the end, it means the number has an equal count of active and inactive bits.

Pseudocode

Here's the pseudocode for the algorithm:

function checkEqualBits(num):
    if num < 0:
        return
    
    print "Number: ", num
    bitDifference = 0
    
    while num > 0:
        if num & 1 == 1:
            bitDifference += 1
        else:
            bitDifference -= 1
        num = num >> 1
    
    if bitDifference == 0:
        print "Equal set and unset bits"
    else:
        print "Not equal set and unset bits"

Algorithm Explanation

1. The function checkEqualBits(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 a counter bitDifference that will represent the difference between the count of active and inactive bits.
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 bitDifference counter is incremented. Otherwise, the bitDifference counter is decremented.
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, if the value of bitDifference is zero, it means the number has an equal count of active and inactive bits. The function prints the result accordingly.

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin
• Rust

// C Program 
// Check if a number has same number of set and unset bits
#include <stdio.h>

// Check whether the given number has the same number of active and passive bits
void checkEqualBits(int num)
{
	if (num < 0)
	{
		return;
	}
	// Display given number
	printf("\n Number : %d", num);
	int bit = 0;
	while (num > 0)
	{
		if (num & 1 == 1)
		{
			// is active bit
			bit++;
		}
		else
		{
			// is an inactive bit
			bit--;
		}
		num = num >> 1;
	}
	if (bit == 0)
	{
		printf("\n Equal set and unset bits \n");
	}
	else
	{
		printf("\n Not equal set and unset bits\n");
	}
}
int main(int argc, char
	const *argv[])
{
	// Test Cases
	// 17 (10001)
	checkEqualBits(17);
	// 9 (1001)
	checkEqualBits(9);
	// 1 (1)
	checkEqualBits(1);
	// 7 (111)
	checkEqualBits(7);
	// 10 (1010)
	checkEqualBits(10);
	return 0;
}

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits

/*
  Java Program 
  Count the number of active and inactive bits of a number
*/
public class Comparison
{
	// Check whether the given number has the same number of active and passive bits
	public void checkEqualBits(int num)
	{
		if (num < 0)
		{
			return;
		}
		// Display given number
		System.out.print("\n Number : " + num);
		int bit = 0;
		while (num > 0)
		{
			if ((num & 1) == 1)
			{
				// is active bit
				bit++;
			}
			else
			{
				// is an inactive bit
				bit--;
			}
			num = num >> 1;
		}
		if (bit == 0)
		{
			System.out.print("\n Equal set and unset bits \n");
		}
		else
		{
			System.out.print("\n Not equal set and unset bits\n");
		}
	}
	public static void main(String[] args)
	{
		Comparison task = new Comparison();
		// Test Cases
		// 17 (10001)
		task.checkEqualBits(17);
		// 9 (1001)
		task.checkEqualBits(9);
		// 1 (1)
		task.checkEqualBits(1);
		// 7 (111)
		task.checkEqualBits(7);
		// 10 (1010)
		task.checkEqualBits(10);
	}
}

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits

// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  Count the number of active and inactive bits of a number
*/
class Comparison
{
	public:
		// Check whether the given number has the same number of active and passive bits
		void checkEqualBits(int num)
		{
			if (num < 0)
			{
				return;
			}
			// Display given number
			cout << "\n Number : " << num;
			int bit = 0;
			while (num > 0)
			{
				if ((num &1) == 1)
				{
					// is active bit
					bit++;
				}
				else
				{
					// is an inactive bit
					bit--;
				}
				num = num >> 1;
			}
			if (bit == 0)
			{
				cout << "\n Equal set and unset bits \n";
			}
			else
			{
				cout << "\n Not equal set and unset bits\n";
			}
		}
};
int main()
{
	Comparison task = Comparison();
	// Test Cases
	// 17 (10001)
	task.checkEqualBits(17);
	// 9 (1001)
	task.checkEqualBits(9);
	// 1 (1)
	task.checkEqualBits(1);
	// 7 (111)
	task.checkEqualBits(7);
	// 10 (1010)
	task.checkEqualBits(10);
	return 0;
}

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits

// Include namespace system
using System;
/*
  C# Program 
  Count the number of active and inactive bits of a number
*/
public class Comparison
{
	// Check whether the given number has the same number of active and passive bits
	public void checkEqualBits(int num)
	{
		if (num < 0)
		{
			return;
		}
		// Display given number
		Console.Write("\n Number : " + num);
		int bit = 0;
		while (num > 0)
		{
			if ((num & 1) == 1)
			{
				// is active bit
				bit++;
			}
			else
			{
				// is an inactive bit
				bit--;
			}
			num = num >> 1;
		}
		if (bit == 0)
		{
			Console.Write("\n Equal set and unset bits \n");
		}
		else
		{
			Console.Write("\n Not equal set and unset bits\n");
		}
	}
	public static void Main(String[] args)
	{
		Comparison task = new Comparison();
		// Test Cases
		// 17 (10001)
		task.checkEqualBits(17);
		// 9 (1001)
		task.checkEqualBits(9);
		// 1 (1)
		task.checkEqualBits(1);
		// 7 (111)
		task.checkEqualBits(7);
		// 10 (1010)
		task.checkEqualBits(10);
	}
}

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits

<?php
/*
  Php Program 
  Count the number of active and inactive bits of a number
*/
class Comparison
{
	// Check whether the given number has the same number of active and passive bits
	public	function checkEqualBits($num)
	{
		if ($num < 0)
		{
			return;
		}
		// Display given number
		echo "\n Number : ". $num;
		$bit = 0;
		while ($num > 0)
		{
			if (($num & 1) == 1)
			{
				// is active bit
				$bit++;
			}
			else
			{
				// is an inactive bit
				$bit--;
			}
			$num = $num >> 1;
		}
		if ($bit == 0)
		{
			echo "\n Equal set and unset bits \n";
		}
		else
		{
			echo "\n Not equal set and unset bits\n";
		}
	}
}

function main()
{
	$task = new Comparison();
	// Test Cases
	// 17 (10001)
	$task->checkEqualBits(17);
	// 9 (1001)
	$task->checkEqualBits(9);
	// 1 (1)
	$task->checkEqualBits(1);
	// 7 (111)
	$task->checkEqualBits(7);
	// 10 (1010)
	$task->checkEqualBits(10);
}
main();

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits

/*
  Node Js Program 
  Count the number of active and inactive bits of a number
*/
class Comparison
{
	// Check whether the given number has the same number of active and passive bits
	checkEqualBits(num)
	{
		if (num < 0)
		{
			return;
		}
		// Display given number
		process.stdout.write("\n Number : " + num);
		var bit = 0;
		while (num > 0)
		{
			if ((num & 1) == 1)
			{
				// is active bit
				bit++;
			}
			else
			{
				// is an inactive bit
				bit--;
			}
			num = num >> 1;
		}
		if (bit == 0)
		{
			process.stdout.write("\n Equal set and unset bits \n");
		}
		else
		{
			process.stdout.write("\n Not equal set and unset bits\n");
		}
	}
}

function main()
{
	var task = new Comparison();
	// Test Cases
	// 17 (10001)
	task.checkEqualBits(17);
	// 9 (1001)
	task.checkEqualBits(9);
	// 1 (1)
	task.checkEqualBits(1);
	// 7 (111)
	task.checkEqualBits(7);
	// 10 (1010)
	task.checkEqualBits(10);
}
main();

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits

#   Python 3 Program 
#   Count the number of active and inactive bits of a number

class Comparison :
	#  Check whether the given number has the same number of active and passive bits
	def checkEqualBits(self, num) :
		if (num < 0) :
			return
		
		#  Display given number
		print("\n Number : ", num, end = "")
		bit = 0
		while (num > 0) :
			if ((num & 1) == 1) :
				#  is active bit
				bit += 1
			else :
				#  is an inactive bit
				bit -= 1
			
			num = num >> 1
		
		if (bit == 0) :
			print("\n Equal set and unset bits ")
		else :
			print("\n Not equal set and unset bits")
		
	

def main() :
	task = Comparison()
	#  Test Cases
	#  17 (10001)
	task.checkEqualBits(17)
	#  9 (1001)
	task.checkEqualBits(9)
	#  1 (1)
	task.checkEqualBits(1)
	#  7 (111)
	task.checkEqualBits(7)
	#  10 (1010)
	task.checkEqualBits(10)

if __name__ == "__main__": main()

 Number :  17
 Not equal set and unset bits

 Number :  9
 Equal set and unset bits

 Number :  1
 Not equal set and unset bits

 Number :  7
 Not equal set and unset bits

 Number :  10
 Equal set and unset bits

#   Ruby Program 
#   Count the number of active and inactive bits of a number

class Comparison 
	#  Check whether the given number has the same number of active and passive bits
	def checkEqualBits(num) 
		if (num < 0) 
			return
		end

		#  Display given number
		print("\n Number : ", num)
		bit = 0
		while (num > 0) 
			if ((num & 1) == 1) 
				#  is active bit
				bit += 1
			else 
				#  is an inactive bit
				bit -= 1
			end

			num = num >> 1
		end

		if (bit == 0) 
			print("\n Equal set and unset bits \n")
		else 
			print("\n Not equal set and unset bits\n")
		end

	end

end

def main() 
	task = Comparison.new()
	#  Test Cases
	#  17 (10001)
	task.checkEqualBits(17)
	#  9 (1001)
	task.checkEqualBits(9)
	#  1 (1)
	task.checkEqualBits(1)
	#  7 (111)
	task.checkEqualBits(7)
	#  10 (1010)
	task.checkEqualBits(10)
end

main()

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits 

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits 

/*
  Scala Program 
  Count the number of active and inactive bits of a number
*/
class Comparison
{
	// Check whether the given number has the same number of active and passive bits
	def checkEqualBits(n: Int): Unit = {
		var num = n;
     	if (num < 0)
		{
			return;
		}
      	
		// Display given number
		print("\n Number : " + num);
		
		var bit: Int = 0;
		while (num > 0)
		{
			if ((num & 1) == 1)
			{
				// is active bit
				bit += 1;
			}
			else
			{
				// is an inactive bit
				bit -= 1;
			}
			num = num >> 1;
		}
		if (bit == 0)
		{
			print("\n Equal set and unset bits \n");
		}
		else
		{
			print("\n Not equal set and unset bits\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Comparison = new Comparison();
		// Test Cases
		// 17 (10001)
		task.checkEqualBits(17);
		// 9 (1001)
		task.checkEqualBits(9);
		// 1 (1)
		task.checkEqualBits(1);
		// 7 (111)
		task.checkEqualBits(7);
		// 10 (1010)
		task.checkEqualBits(10);
	}
}

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits

/*
  Swift 4 Program 
  Count the number of active and inactive bits of a number
*/
class Comparison
{
	// Check whether the given number has the same number of active and passive bits
	func checkEqualBits(_ n: Int)
	{
      	var num = n;
		if (num < 0)
		{
			return;
		}
		// Display given number
		print("\n Number : ", num, terminator: "");
		var bit: Int = 0;
		while (num > 0)
		{
			if ((num & 1) == 1)
			{
				// is active bit
				bit += 1;
			}
			else
			{
				// is an inactive bit
				bit -= 1;
			}
			num = num >> 1;
		}
		if (bit == 0)
		{
			print("\n Equal set and unset bits ");
		}
		else
		{
			print("\n Not equal set and unset bits");
		}
	}
}
func main()
{
	let task: Comparison = Comparison();
	// Test Cases
	// 17 (10001)
	task.checkEqualBits(17);
	// 9 (1001)
	task.checkEqualBits(9);
	// 1 (1)
	task.checkEqualBits(1);
	// 7 (111)
	task.checkEqualBits(7);
	// 10 (1010)
	task.checkEqualBits(10);
}
main();

 Number :  17
 Not equal set and unset bits

 Number :  9
 Equal set and unset bits

 Number :  1
 Not equal set and unset bits

 Number :  7
 Not equal set and unset bits

 Number :  10
 Equal set and unset bits

/*
  Kotlin Program 
  Count the number of active and inactive bits of a number
*/
class Comparison
{
	// Check whether the given number has the same number of active and passive bits
	fun checkEqualBits(n: Int): Unit
	{
        var num : Int = n;
		if (num < 0)
		{
			return;
		}
		// Display given number
		print("\n Number : " + num);
		var bit: Int = 0;
		while (num > 0)
		{
			if ((num and 1) == 1)
			{
				// is active bit
				bit += 1;
			}
			else
			{
				// is an inactive bit
				bit -= 1;
			}
			num = num shr 1;
		}
		if (bit == 0)
		{
			print("\n Equal set and unset bits \n");
		}
		else
		{
			print("\n Not equal set and unset bits\n");
		}
	}
}
fun main(args: Array <String> ): Unit
{
	var task: Comparison = Comparison();
	// Test Cases
	// 17 (10001)
	task.checkEqualBits(17);
	// 9 (1001)
	task.checkEqualBits(9);
	// 1 (1)
	task.checkEqualBits(1);
	// 7 (111)
	task.checkEqualBits(7);
	// 10 (1010)
	task.checkEqualBits(10);
}

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits

fn main()
{
	// Test Cases
	// 17 (10001)
	check_equal_bits(17);
	// 9 (1001)
	check_equal_bits(9);
	// 1 (1)
	check_equal_bits(1);
	// 7 (111)
	check_equal_bits(7);
	// 10 (1010)
	check_equal_bits(10);
}
fn check_equal_bits(n: i32)
{
  	let mut num: i32 = n;
	if num < 0
	{
		return;
	}
	// Display given number
	print!("\n Number : {}", num);
	let mut bit: i32 = 0;
	while num > 0
	{
		if num & 1 == 1
		{
			bit += 1;
		}
		else
		{
			bit -= 1;
		}
		num = num >> 1;
	}
	if bit == 0
	{
		print!("\n Equal set and unset bits \n");
	}
	else
	{
		print!("\n Not equal set and unset bits\n");
	}
}

 Number : 17
 Not equal set and unset bits

 Number : 9
 Equal set and unset bits

 Number : 1
 Not equal set and unset bits

 Number : 7
 Not equal set and unset bits

 Number : 10
 Equal set and unset bits

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 count of active bits is not equal to the count of inactive bits.
   • The output is "Number: 17\nNot equal set and unset bits".

2. For the number 9:

   • Binary representation: 1001
   • Active bits: 2 (bit positions 0 and 3)
   • Inactive bits: 2 (bit positions 1 and 2)
   • The count of active bits is equal to the count of inactive bits.
   • The output is "Number: 9\nEqual set and unset bits".

3. For the number 1:

   • Binary representation: 1
   • Active bits: 1 (bit position 0)
   • Inactive bits: 0
   • The count of active bits is not equal to the count of inactive bits.
   • The output is "Number: 1\nNot equal set and unset bits".

4. For the number 7:

   • Binary representation: 111
   • Active bits: 3 (bit positions 0, 1, and 2)
   • Inactive bits: 0
   • The count of active bits is not equal to the count of inactive bits.
   • The output is "Number: 7\nNot equal set and unset bits".

5. For the number 10:

   • Binary representation: 1010
   • Active bits: 2 (bit positions 1 and 3)
   • Inactive bits: 2 (bit positions 0 and 2)
   • The count of active bits is equal to the count of inactive bits.
   • The output is "Number: 10\nEqual set and unset bits".

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.