# Brian Kernighan’s Algorithm to count set bits in an integer

Given an integer, count its set bits.

For example,

Input: n = -1 (11..1111)
Output: The number of set bits in -1 is 32

Input: n = 16 (00001000)
Output: The number of set bits in 16 is 1

A simple solution would be to consider every bit (set or unset) till last set bit in a number and maintain a counter to count set bits.

C++ implementation –

Output:

16 in binary is 00010000
The number of set bits in 16 is 1

The naive approach requires one iteration per bit, until no more bits are set. So on a 32-bit word with only the high set, it will go through 32 iterations.

We can use Brian Kernighan’s algorithm to improve performance of above naive algorithm. The idea is to consider only set bits of the integer by turning off the rightmost set bit of given number after considering it, so next iteration of loop will consider next rightmost bit.

We know that the expression (n & (n-1)) will turn off the rightmost set bit of given number. (n-1) will have all the bits flipped after the rightmost set bit of n (including the rightmost set bit).
So (n & (n-1)) will result in last bit flipped of n.
For example, consider number 52 which is equal to 00110100 in binary and its total set bits are 3.

1st iteration of loop: n = 52

00110100   &          (n)
00110011              (n-1)
~~~~~~~~
00110000

2nd iteration of loop: n = 48

00010000   &          (n)
00101111              (n-1)
~~~~~~~~
00100000

3nd iteration of loop: n = 32

00100000   &          (n)
00011111              (n-1)
~~~~~~~~
00000000              (n = 0)

C++ implementation –

Output:

-1 in binary is 11111111111111111111111111111111
The number of set bits in -1 is 32

Brian Kernighan’s method goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.

GCC also provides a built-in function int __builtin_popcount (unsigned int n) that returns the number of set bits in n.

C++ implementation –

Output:

The number of set bits in 16 is 1

GCC also provides two other built-in function int __builtin_popcountl (unsigned long) and int __builtin_popcountll (unsigned long long) similar to __builtin_popcount, except their argument type is unsigned long and unsigned long long respectively.

We can also use std::bitset::count that returns the number of bits in the bitset that are set.

C++ implementation –

Output:

The number of set bits in 30 (00011110) is 4

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂