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"?

Sooksoon

Think about long subtraction and "borrowing". – Fields

It clears the rightmost bit because the rightmost bit of n - 1 is never the same as n. – Waggish

Kernighan's bit-count trick! – Dune

Bit twiddling tricks generally should be done with unsigned types in case your machine doesn't use two's complement for signed types (or in case the compiler tries to do some clever optimization based on the knowledge that the standard doesn't require two's complement for signed types). – Dru

This question asks about n = n & (n - 1), in other words n &= (n-1). The suggested "answered" question asked for something else, as said in its title: what does n & (n-1) do. The purpose of the former one is removing the rightmost value-1 bit, whereas the latter one is to check whether n is the power of 2. I can see the point that the two expressions look similar and their truth tables are the same, but these two questions, and therefore answers, are undoubtedly different – Laundes

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.

Konstance

Does this hold for negative values if the platform uses signed magnitude representation rather than two's complement? – Dru

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.

Channa