Brian Kernighan's technique to count set bits

Brian Kernighan's iterative technique to count set bits in an integer is described in the link below. Just a little help here to see how it works.

Let's start with an example.

Say for x = 9, you want to count number of set bits (9 = (1001) base 2)

Initialize a count variable to 0;

while (x > 0) {

Compute x - 1 = 8. 

Compute x = x & ( x - 1) 

increment count

}

Number of set bits = final value of "count" variable. Now, to see how it works, it is a good idea to rely on a method of back propagation. If you observe carefully, the stopping condition for the algorithm is when x = 0. It is good to understand when x becomes zero. x becomes zero during the iteration in which the value of x is a power of 2 which would also be when only one bit would be set in x.

http://www.geeksforgeeks.org/count-set-bits-in-an-integer/