**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

**Count set bits in an integer: **We’ll look at Brian Kernighan’s Algorithm and see how it works in C++ and Python.

- Brute-Force Solution (Naïve Approach)
- Brian Kernighan’s Algorithm to calculate set bits in an integer
- Implementing Brian Kernighan’s Algorithm in Python
- Implementing Brian Kernighan’s Algorithm in C++
- To Count Set Bits in an Integer Using GCC built-in function

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

**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++

**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**:

- Python Program to Count Set Bits in a Number
- Python Program to Count the Number of Digits Present In a Number
- Python Program to Move all Zeros present in an Array/List to the End
- Python Program to Find the Missing Number in an array/list
- Python Program to Find the Odd Occurring Element in an Array/list
- Python Program to Find a Pair with the Given Sum in an Array
- Python Program to Count the Frequency of Words Appearing in a String Using a Dictionary