## DEV Community

Ayan Banerjee

Posted on • Updated on • Originally published at csposts.com

# Count Number of Set Bits of an Integer using Brian-Kernighan Method

Count the number of set bits of an integer.

Examples:

Input: 31
Output: 5
Explanation: Binary representation of 31 is 11111

Input: 42
Output: 3
Explanation: Binary representation of 42 is 101010

## Approach-1: Naive

Naive algorithm is to use the binary representation of the number and count the number of set bits.

C++ code:

``````#include<iostream>
using namespace std;

int countSetBits(int n) {
int count = 0;
while (n > 0) {
count += n & 1; // check if the last bit is set
n = n >> 1; // right shift by 1 is equivalent to division by 2
}
return count;
}

int main() {
cout << "Number of set bits of " << 31 << " is " << countSetBits(31) << "\n";
cout << "Number of set bits of " << 42 << " is " << countSetBits(42) << "\n";
return 0;
}
``````

Python code:

``````def count_set_bits(n):
count = 0
while n > 0:
count += n & 1
n = n >> 1
return count

if __name__ == '__main__':
print('Number of set bits of', 31, 'is', count_set_bits(31))
print('Number of set bits of', 42, 'is', count_set_bits(42))
``````

Time Complexity: `O(logN)` where N is the number
Space Complexity: `O(1)` as we are not using any extra space

## Approach-2: Brian Kernighan Algorithm

`n = n & (n - 1)` clears the rightmost set bit. Let us take a look at some
examples.

``````n           => 101010
n - 1       => 101001
---------------------
n & (n - 1) => 101000
``````

`n` is updated to `101000` now.

``````n           => 101000
n - 1       => 100111
---------------------
n & (n - 1) => 100000
``````

`n` is updated to `100000` now.

``````n           => 100000
n - 1       => 011111
--------------------------
n & (n - 1) => 000000
``````

`n` is now 0.

Thus, we need only 3 iterations to find the count of set bits.

C++ code:

``````#include<iostream>
using namespace std;

int countSetBits(int n) {
int count = 0;
while (n > 0) {
n = n & (n - 1); // clear the right-most bit
++count;
}
return count;
}

int main() {
cout << "Number of set bits of " << 31 << " is " << countSetBits(31) << "\n";
cout << "Number of set bits of " << 42 << " is " << countSetBits(42) << "\n";
return 0;
}
``````

Python code:

``````def count_set_bits(n):
count = 0
while n > 0:
n = n & (n - 1)  # clear the right most bit
count += 1
return count

if __name__ == '__main__':
print('Number of set bits of', 31, 'is', count_set_bits(31))
print('Number of set bits of', 42, 'is', count_set_bits(42))
``````

Time Complexity: `O(logN)` when N has all of its bit set
Space Complexity: `O(1)` as we are not using any extra space