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
- The function
checkEqualBits(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 a counter
bitDifference
that will represent the difference between the count of active and inactive bits. - 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
bitDifference
counter is incremented. Otherwise, thebitDifference
counter is decremented. - The number is right-shifted by one position (
num = num >> 1
) to process the next bit in the next iteration. - 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 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;
}
Output
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);
}
}
Output
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;
}
Output
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);
}
}
Output
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();
Output
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();
Output
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()
Output
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()
Output
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);
}
}
Output
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();
Output
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);
}
Output
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");
}
}
Output
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:
-
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".
-
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".
-
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".
-
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".
-
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.
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