BBLN - 2 months ago 29

C++ Question

I need some explaination 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

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.