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.
- By using in build library
- 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.
i.e
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; }