Brian Kernighan's Algorithm

#beginners #algorithms #cpp

When i was solving some katas in Codewars, I come across a question about bit counting.

Write a function that takes an integer as input, and returns the number of bits that are equal to one in the binary representation of that number. You can guarantee that input is non-negative.
Example: The binary representation of 1234 is 10011010010, so the function should return 5 in this case

I solve the question and after looking at peoples code i saw an answer like

And a comment below like

So I look up a little bit and this is what I got..

Lets go to beginning, the first thing that comes to my mind when I look at the question is counting every bit inside of binary representation of the integer and add it to counter then return the value of counter.

For that i need to iterate from the bit[0] to bit[last - 1]

1000 0001 1001 ->  12 times
0010 1111 0111 ->  10 times
     1100 1010 ->   8 times

But in Brian Kerninghan’s algorithm things become different.

Lets check first what is &(BITWISE AND) operator does.

If both bits in same column are set BITWISE AND operation leave that bit set(1), but if any of them is cleared(0) in the same column BITWISE AND leaves that bit cleared(0).

  1011 1001
  0101 0110
&-----------
  0001 0000

When we write an if statement

if (a >= b & b >= c){
 //do something
}

(a >= b) needs to be TRUE(1)
(b >= c) needs to be TRUE(1)

if statement becomes

if (1 & 1 == 1)

than our condition becomes true.

In Brian Kerninghan’s Algorithm he uses n & (n - 1) when n != 0

So lets check what happens for value 12

--12 != 0
12 & 11 = 8
0x1100 & 0x1011 = 0x1000
counter = 1;

--8 != 0
8 & 7 = 0
0x1000 & 0x0111 = 0x0000
counter = 2;

lets look at 13

--13 != 0
13 & 12 = 12
0x1110 & 0x1100 = 0x1100
counter = 1;

--12 != 0
12 & 11 = 8
0x1100 & 0x1011 = 0x1000
counter = 2;

--8 != 0
8 & 7 = 0
0x1000 & 0x0111 = 0x0000
counter = 3;

When we look carefully every time that loop runs, the first bit on the right (rightmost set bit) will disappear after &(BITWISE AND) operation.

12 ->> 0x1100 -> 0x1000 -> 0x0000           (2 times)
13 ->> 0x1110 -> 0x1100 -> 0x1000 -> 0x0000 (3 times)
9  ->> 0x1001 -> 0x1000 -> 0x0000           (2 times)

If we have an unsigned value for example 255 (0x11111111) in the 1st approach we have to iterate 8 times to get the result and in Brian Kerninghan’s Algorithm it is also 8 times.

But in any cases differ than all the bits are set, Brian Kerninghan’s approach becomes way more efficient.

1st approach -> 0x11001111 -> 8 times
2nd approach -> 0x11001111 -> 6 times

1st approach -> 0x10000011 -> 8 times
2nd approach -> 0x10000011 -> 3 times

USEFUL LINKS

Count set bits in an integer | GeeksforGeeks