Brian Kernighan’s Algorithm to Count Set bits of a Number in C++ and Python

Brian Kernighan’s Algorithm to count set bits in an integer in C++ and Python

CPP Programming, Python / By

Brian Kernighan’s Algorithm to count the number of set bits in an integer: Given a number, the task is to count the set bits of the given number using Brian Kernighan’s Algorithm in C++ and Python.

Brian Kernighan’s Algorithm to Count Set bits of a Number in C++ and Python

We’ll look at Brian Kernighan’s Algorithm and see how it works in C++ and Python.

Drive into Python Programming Examples and explore more instances related to python concepts so that you can become proficient in generating programs in Python Programming Language.

Example1:

Input:

given number =43

Output:

The total number of set bits in the given number  43  : 
4

Example2:

Input:

given number =64

Output:

The total number of set bits in the given number  64  : 
1

Example3:

Input:

given number =4322

Output:

The total number of set bits in the given number  4322  : 
5

First, we implement the brute force solution for the above program

Brute-Force Approach (Naïve Approach)

A simple method is to take each bit into consideration in a number (set or unset) and hold a counter to track the set bits.

Approach:

  • Set the variable to say count to 0 to count the total number of set bits.
  • We utilize the while loop.
  • We’ll keep going till the number is bigger than zero (Condition of while statement)
  • Using the % operator, we will determine whether the last check bit is set or not.
  • If the check bit is 1, it indicates that the bit is set, and we increment the count.
  • Divide the given number by 2.
  • Print the count.

Below is the implementation:

def countSetBit(numb):
    # checking if the given number is greater than 1
    if numb > 1:
      # Set the variable say setbitcount to 0 to count the total number of set bits.
        setbitcount = 0
        # looping till number greater than 0 using while loop
        while(numb > 0):
            # We will get the last check bit whether it is set bit or not using % operator
            checkbit = numb % 2
            # checking if the check bit is 1 or not
            # if the check bit is 1 then increment the setbitcount
            if(checkbit == 1):
                setbitcount = setbitcount+1
            # divide the number by 2
            numb = numb//2
    # return the setbitcount
    return setbitcount


# Driver code
given_numb = 235
# passing given number to countSetBit function to
# count the total number of set bits in the given number
print("The total number of set bits in the given number ", given_numb, " : ")
print(countSetBit(given_numb))

Output:

The total number of set bits in the given number  235  : 
6

The brute-force strategy described above requires one repetition per bit until no more set bits remain. So it goes through 32 iterations on a 32–bit word with only the high-bit set.

Brian Kernighan’s Algorithm to calculate set bits in an integer

We may apply Brian Kernighan’s technique to improve the performance of the naive algorithm described above. The concept is to only consider an integer’s set bits by turning off its rightmost set bit (after counting it) so that the next iteration of the loop only considers the next rightmost bit.

To turn off the rightmost set bit of a number n, use the formula n & (n-1). This is because the formula n-1 flips all the bits following the rightmost set bit of n, including the rightmost set bit itself. As a result, n & (n-1) results in the last bit of n being flipped.

Implementing Brian Kernighan’s Algorithm to count the number of set bits in an integer in Python

implementation of Brian Kernighan's Algorithm in Python

Below is the implementation of Brian Kernighan’s Algorithm to set bits in a Python:

def countSetBit(numb):
    # checking if the given number is greater than 1
    if numb > 1:
      # Set the variable say setbitcount to 0 to count the total number of set bits.
        setbitcount = 0
        # looping till number greater than 0 using while loop
        while(numb > 0):
            numb = numb & (numb-1)
            # increment the set bit count
            setbitcount = setbitcount+1
    # return the setbitcount
    return setbitcount


# Driver code
given_numb = 4322
# passing given number to countSetBit function to
# count the total number of set bits in the given number
print("The total number of set bits in the given number ", given_numb, " : ")
print(countSetBit(given_numb))

Output:

The total number of set bits in the given number  4322  :  5

Time Complexity: O(logn)

Implementing Brian Kernighan’s Algorithm to count the number of set bits in an integer in C++

Brian Kernighan’s Algorithm to count number of set bits in an integer in c++
Below is the implementation of Brian Kernighan’s Algorithm to set bits in a C++:

#include <iostream>
using namespace std;
// function which returns the total number of set bits in
// the given number
int countSetBit(int numb)
{ // Set the variable say setbitcount to 0 to count the
  // total number of set bits.
    int setbitcount = 0;
    // checking if the given number is greater than 1
    if (numb > 1) {
        // looping till number greater than 0 using while
        // loop
        while (numb > 0) {          
            numb = numb & (numb - 1);
            // increment the set bit count
            setbitcount++;
        }
    }
    // return the setbitcount
    return setbitcount;
}
int main()
{
    // given number
    int given_numb = 4322;
    // passing given number to countSetBit function to
    // count the total number of set bits in the given
    // number
    cout << "The total number of set bits in the given "
            "number "
         << given_numb << " : " << endl;
    cout << countSetBit(given_numb);

    return 0;
}

Output:

The total number of set bits in the given number  4322  : 
5

Brian Kernighan’s algorithm iterates as many times as there are set bits. So, if we have a 32–bit word with only the high bit set, it will only be looped once.

To Count Set Bits in an Integer Using GCC built-in function

GCC also implements a built-in function to get no of set bits in an integer,int __builtin_popcount(unsigned int n) that returns the total number of set bits in n. The below C++ program illustrates it clearly:

#include <iostream>
using namespace std;
 
int main()
{
    int n = 16;
    cout << "The total number of set bits in " << n << " is "
         << __builtin_popcount (n) << endl;
 
    return 0;
}

Output: 

The total number of set bits in 16 is 1

Also, GCC furnishes two other built-in functions, int __builtin_popcountl (unsigned long) and int __builtin_popcountll (unsigned long long), same as __builtin_popcount, except their argument type is unsigned long and unsigned long long, each.

Related Programs: