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