Counting number of bits: How does this line work ? n=n&(n-1); [duplicate]

Question

I need some explanation how this specific line works.
I know that this function counts the number of 1's bits, but how exactly this line clears the rightmost 1 bit?

int f(int n) {
    int c;
    for (c = 0; n != 0; ++c) 
        n = n & (n - 1);
    return c;
}

Can some explain it to me briefly or give some "proof"?

Answer 1

Any unsigned integer 'n' will have the following last k digits: One followed by (k-1) zeroes: 100...0 Note that k can be 1 in which case there are no zeroes.

(n - 1) will end in this format: Zero followed by (k-1) 1's: 011...1

n & (n-1) will therefore end in 'k' zeroes: 100...0 & 011...1 = 000...0

Hence n & (n - 1) will eliminate the rightmost '1'. Each iteration of this will basically remove the rightmost '1' digit and hence you can count the number of 1's.

Answer 2

I've been brushing up on bit manipulation and came across this. It may not be useful to the original poster now (3 years later), but I am going to answer anyway to improve the quality for other viewers.

What does it mean for n & (n-1) to equal zero?

We should make sure we know that since that is the only way to break the loop (n != 0). Let's say n=8. The bit representation for that would be 00001000. The bit representation for n-1 (or 7) would be 00000111. The & operator returns the bits set in both arguments. Since 00001000 and 00000111 do not have any similar bits set, the result would be 00000000 (or zero). You may have caught on that the number 8 wasn't randomly chosen. It was an example where n is power of 2. All powers of 2 (2,4,8,16,etc) will have the same result.

What happens when you pass something that is not an exponent of 2? For example, when n=6, the bit representation is 00000110 and n-1=5 or 00000101.The & is applied to these 2 arguments and they only have one single bit in common which is 4. Now, n=4 which is not zero so we increment c and try the same process with n=4. As we've seen above, 4 is an exponent of 2 so it will break the loop in the next comparison. It is cutting off the rightmost bit until n is equal to a power of 2.

What is c?

It is only incrementing by one every loop and starts at 0. c is the number of bits cut off before the number equals a power of 2.