DEV Community

Ayan Banerjee
Ayan Banerjee

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

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

#cpp #python #interview #career

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; }
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

n is updated to 101000 now.

n => 101000 n - 1 => 100111 --------------------- n & (n - 1) => 100000
Enter fullscreen mode Exit fullscreen mode

n is updated to 100000 now.

n => 100000 n - 1 => 011111 -------------------------- n & (n - 1) => 000000
Enter fullscreen mode Exit fullscreen mode

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; }
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)