Counting the number of set bits in an integer
Specific to C++
a) Counting number of set bits using C++ bitset class template.
Using C++ bitset we can construct a bitset that initializes the rightmost N bit positions to the bit values corresponding to a number.
b) Counting number of set bits using GCC provided built-in function __builtin_popcount (unsigned int x).
GCC (GNU Compiler Collection) provides numerous built-in functions, one of which is __builtin_popcount (unsigned int x).
This function returns number of set bits in an integer.
c) Counting the number of set bits using right shift and logical AND operation.
Example: Consider finding number of set bits in number 11 (Binary 1011).
We perform a logical AND operation between 11 (1011) and 1 (0001); since the result if greater than 1
it means the rightmost bit is set to 1.
Thus we increase the number of set bits. We perform a right shift operation on 11 and again perform a
logical AND operation.
If the result of the logical AND operation is greater than 1 we increase the ‘1’ bit count and continue to perform right shift and logical AND operations.
The right shift and logical AND operations continue till number till it is greater than zero. Thus we get the ‘1’ (set) bit count in a number.
C++: Counting the number of set bits in an integer.
#include<iostream>
#include<bitset>
#include<cstdio>
using namespace std;
class Bits {
public:
// Finding the number of set bits using bitset
void CountSetBits(int num) {
bitset<32> foo(num);
cout << "\n\nNumber : " << num << endl;
cout << "Binary representation : " << foo << endl;
cout << "Set bits using bitset : " << foo.count() << endl;
cout << "Set bits using builtin_popcount : " << __builtin_popcount(num) << endl;
/* Note : int __builtin_popcountl (unsigned long)
int __builtin_popcountll (unsigned long long) */
// Counting set bits using right shift and logical AND operation
int set_bits = 0;
while (num) {
if (num & 1)
set_bits++;
num = num >> 1;
}
cout << "Set bits using right-shift and logical AND operation : " << set_bits << endl;
}
};
int main() {
Bits b;
b.CountSetBits(234);
b.CountSetBits(512);
b.CountSetBits(10);
b.CountSetBits(65535);
return 0;
}
Output
Number : 234
Binary representation : 00000000000000000000000011101010
Set bits using bitset : 5
Set bits using builtin_popcount : 5
Set bits using right-shift and logical AND operation : 5
Number : 512
Binary representation : 00000000000000000000001000000000
Set bits using bitset : 1
Set bits using builtin_popcount : 1
Set bits using right-shift and logical AND operation : 1
Number : 10
Binary representation : 00000000000000000000000000001010
Set bits using bitset : 2
Set bits using builtin_popcount : 2
Set bits using right-shift and logical AND operation : 2
Number : 65535
Binary representation : 00000000000000001111111111111111
Set bits using bitset : 16
Set bits using builtin_popcount : 16
Set bits using right-shift and logical AND operation : 16