Close

# Counting the set bits in a number

Given an integer, how do we count the number of set (1) bits?

For example the number 37 has 3 set bits in it’s binary representation (0010 0101)

Method#1: Simple

In this method we perform & operation between the number and 1 to get the last bit (Least Significant Bit or LSB). If it is 1 we increment the count. In the next iteration we right shift the number by one bit and repeat the same operation until the number becomes 0.

`public static int getSetBitCount(int num)    {        int count = 0;        while( num > 0)        {            if( (num & 1) == 1)                count++;            num = num >> 1;        }        return count;    }`

This method has a drawback that even if there less number of set bits, we have to go through all the bits to count the set bits.
For example If the given number is 129 ( 1000 0001).  It unnecessarily goes though all the 0s between the first and last 1s.
Next method overcomes this drawback.

Method#2: Kernighan & Ritchie Method

This method is a slight improvement of the previous method where it skips the zeroes wherever they appear.

This method is based on the observation that performing a bit-wise & operation between num and (num-1) clears the right most set bit.

For example if num = 39
0010 0111
0010 0110
———-&
0010 0110

The number of iterations in this algorithm is based on the number of set bits. If number is 129 we can find the set bits in just two iterations.

1000 0001 = 129
1000 0000 = 128
———-&
1000 0000 = 128
0111 1111 = 127
————-&
0000 0000

`public static int getSetBitCount(int num)    {        int count = 0;        while( num > 0)        {            num = num & (num-1);            count++;        }        return count;    }`

` `