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

Possible duplicate of [Bits counting algorithm (Brian Kernighan) in an integer time complexity](http://stackoverflow.com/questions/12380478/bits-counting-algorithm-brian-kernighan-in-an-integer-time-complexity) — OhadR, Dec 05 '16 at 14:09

Peter Lawrey · Accepted Answer · 2012-09-12T07:40:08.843

37

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

edited Sep 12 '12 at 07:40

answered Sep 12 '12 at 07:23

Peter Lawrey

525,659
79
751
1,130

You're fast, was only half-way through pretty much the same description :) – pap Sep 12 '12 at 07:24
@pap I jump onto questions rather quick, should stop that. ;) – Peter Lawrey Sep 12 '12 at 07:26
3

The reason being `1000... - 1 = 0111...` so bitwise and gives you `0000...` – verdesmarald Sep 12 '12 at 07:34

score 2 · Answer 2 · answered Apr 10 '17 at 02:54

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

Please explain the logic behind Kernighan's bit counting algorithm

2 Answers2

Linked