Count set bits in an integer using Brian Kernighan Algorithm in C++

This article will guide you on how to write an efficient program to count the number of 1s in the binary representation of an integer using Brian Kernighan’s algorithm in C++. Brian Kernighan’s algorithm takes time equal to the number of set bits in a given integer. So if a number has only two set bits then the loop is going to run two times only. In a binary number, 1s are called ‘set bits’, and 0s are called ‘unset bits’.

Approach:

The algorithm is as follows:

1) Initialize a variable(say count)= zero(0)
2) If the integer which is taken as input(say n) is not zero
a)Perform bitwise AND (&) with n-1 and assign the value to n
n = n&(n-1)
b)Increment count by one
c)Go to step 2

3)Else return  count

Implementation of Brian Kernighan’s Algorithm using C++:

Below is the required C++ code to demonstrate the algorithm:

// C++ program to Count set 
// bits in an integer 
//using Brian Kernighan algorithm
#include <bits/stdc++.h> 
using namespace std; 

unsigned int count_set_Bits(int n) 
{ 
       unsigned int count = 0; 
       while (n>0) { 
          n &= (n - 1); 
          count++; 
       } 
      return count; 
} 

/* Program to test function countSetBits */
int main() 
{ 
  int z = 40; 
  cout << count_set_Bits(z); 
  return 0; 
} 


Output:

2

Example:

Let us take a value of n=40. If n=40 the binary representation is: 00….0101000 We can observe that there are two set bits in 40. If we ignore the leading 0 bits, then the binary representation is:

n=40 : 101000

n-1=39 : 100111

n&(n-1): 100000

We perform the operation n=n & (n-1) .The result which we obtain is 32 since 32 in binary is 100000. The value of count is incremented by 1. We perform the bitwise AND again since 32 is greater than 0.

n=32:   100000

n-1=31: 011111

n&(n-1):000000

The value of count is incremented by one again and the value of count becomes 2.Since n is zero now, we return the value of count which is 2.

Time Complexity is  O(log n).
Thank you for reading. I hope this helps.

Leave a Reply

Your email address will not be published. Required fields are marked *