Hamming weight

[hoity]

Can anybody please explain the following code portion here.

  int count_set_bits(int N)
{
    int result;
    while(N)
    {
        result++;
        N &=N-1;
    }
    return result;
}

[MiiNiPaa]

Well, it counts number of set bit in integer.
while(N) is the same as while(N != 0)
operation N &= N-1 will unset least significant bit in number
By doing it in a loop and incrementing counter we will get number of set bits.

[vlad from moscow]

It is simply to consider the binary representation of a number. For example let N is equal to 12 that is 1100 in binary.

The first check while( N ) says that at least one bit is set in the number. Then 1 is subtracted from N. N will be equal to

1011

Because in the original N all bits after the second bit were equal to 0 then
N & N -1 will store only bits equal to 1 before the second bit that is the result will be

1100
&
1011
-----
1000

Thus the function counts the number of bits that are set to 1.

Only the function contains a bug. Variable result shall be initialized

int result = 0;

[hoity]

Thanks everybody :D