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 –
 

Download   Run Code

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 –
 

Download   Run Code

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 –
 

Download   Run Code

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 –
 

Download   Run Code

Output:

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

 

References:
https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
systemBuilder
Guest
systemBuilder

This is a really crappy algorithm I designed one that can count 32 bits in 17 instructions maximum, constant time.

wpDiscuz