BBLN BBLN - 5 days ago 5
C++ Question

How does this line work ? n=n&(n-1);

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.

Comments