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.

Number_Of_Set_Bits



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


Copyright (c) 2019-2022, Algotree.org.
All rights reserved.