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 — OhadR
– OhadR, Commented Dec 5, 2016 at 14:09

Peter Lawrey · Accepted Answer · 2012-09-12 07:40:08Z

39

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, 2012 at 7:40

answered Sep 12, 2012 at 7:23

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

pap Over a year ago

You're fast, was only half-way through pretty much the same description :)

Peter Lawrey Over a year ago

@pap I jump onto questions rather quick, should stop that. ;)

verdesmarald Over a year ago

The reason being 1000... - 1 = 0111... so bitwise and gives you 0000...

Siva Prakash · Accepted Answer · 2017-04-10 02:54:22Z

4

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

answered Apr 10, 2017 at 2:54

Siva Prakash

5,04739 silver badges27 bronze badges

Collectives™ on Stack Overflow

Please explain the logic behind Kernighan's bit counting algorithm

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related