CODEWITHSUNDEEP
javaalgorithmbit-manipulationbit
Geek
Geek

Reputation: 27203

Please explain the logic behind Kernighan's bit counting algorithm

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");
}

Upvotes: 24

Views: 5725

Answers (2)

Siva Prakash
Siva Prakash

Reputation: 4997

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

Upvotes: 4

Peter Lawrey
Peter Lawrey

Reputation: 533710

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

Upvotes: 39

Related Questions