c++ - Counting number of bits: How does this line work ? n=n&(n-1); -
this question has answer here: n & (n-1) expression do? [duplicate] 4 answers i need explanation how specific line works. know function counts number of 1's bits, how line clears rightmost 1 bit? int f(int n) { int c; (c = 0; n != 0; ++c) n = n & (n - 1); return c; } can explain me briefly or give "proof"? any unsigned integer 'n' have following last k digits: 1 followed (k-1) zeroes: 100...0 note k can 1 in case there no zeroes. (n - 1) end in format: 0 followed (k-1) 1's: 011...1 n & (n-1) therefore end in 'k' zeroes: 100...0 & 011...1 = 000...0 hence n & (n - 1) eliminate rightmost '1'. each iteration of remove rightmost '1' digit , hence can count number of 1's.