Problem statement:
You are given a number, return the number of set bits if that number, when represented that number in binary format.
Example:
If the input number is 10, it’s binary representation is 1010. The number of set bits are 2.
This problem can be solved in 2 ways.
1. By using in build library
2. By bit manipulation
We shall see both of the methods.
By using inbuilt library function:
C++ provide a inbuilt function bitset <32>()
It will convert the int value to binary and use “count()” method to get the number of set bits.
Eg: bitset<32>(n).count()
By using Bit Manipulation:
In bit manipulation, we shall use bitwise and (&) and right shift operation.
Bitwise and (&):
To know the present bit value, is set or unset bit , you need to do a bitwise and(&) with the current bit.
1
&1
-------
1
1
&0
-------
0
To move to the next bit, use right shift operator (>>).
Below is how to count the number of set bits:
1010
&1
---------
0
>>1
101
&1
---------
1
>>1
10
&1
---------
0
>>1
1
&1
---------
1
So the total number of set bits are 2.
Solution in C++
#include<iostream>
using namespace std;
void count_set_bits_by_bit_wise(uint32_t n)
{
int res=0;
while (n!=0)
{
res += n&1;
n = n >> 1;
}
cout<<"The number of set bits by using library function is = "<< res<<endl;
}
void count_set_bits_by_lib_function(uint32_t n)
{
cout<<"The number of set bits by using library function is = "<< bitset<32>(n).count()<<endl;
}
int main()
{
uint32_t num = 20;
cout<< "The num in int value is = " <<num<<endl;
cout<< "The num in binary format is = " << bitset<32>(num)<<endl;
count_set_bits_by_bit_wise(num);
count_set_bits_by_lib_function(num);
return 0;
}