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

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.