Please explain the logic behind Kernighan's bit counting algorithm

Question

This question directly follows after reading through Bits counting algorithm (Brian Kernighan) in an integer time complexity . The Java code in question is

int count_set_bits(int n) {   int count = 0;     while(n != 0) {       n &= (n-1);       count++;     }  } 

I want to understand what n &= (n-1) is achieving here ? I have seen a similar kind of construct in another nifty algorithm for detecting whether a number is a power of 2 like:

if(n & (n-1) == 0) {     System.out.println("The number is a power of 2"); } 

Answer 1

Stepping through the code in a debugger helped me.

If you start with

n = 1010101 & n-1=1010100 => 1010100 n = 1010100 & n-1=1010011 => 1010000 n = 1010000 & n-1=1001111 => 1000000 n = 1000000 & n-1=0111111 => 0000000 

So this iterates 4 times. Each iteration decrements the value in such a way that the least significant bit that is set to 1 disappears.

Decrementing by one flips the lowest bit and every bit up to the first one. e.g. if you have 1000....0000 -1 = 0111....1111 not matter how many bits it has to flip and it stops there leaving any other bits set untouched. When you and this with n the lowest bit set and only the lowest bit becomes 0

Answer 2

Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. In this way we can unset 1s one by one from right to left in loop.

The number of times the loop iterates is equal to the number of set bits.

Source : Brian Kernighan's Algorithm