计数位数:这条线如何工作？N = N&第(n-1);

Question

我需要解释一下这条特定的线是如何工作的.
我知道这个函数计算1位的数量,但这条线究竟是如何清除最右边的1位？

int f(int n) {
    int c;
    for (c = 0; n != 0; ++c) 
        n = n & (n - 1);
    return c;
}

有人可以简单地向我解释一下或给出一些"证明"吗？

Answer 1

任何无符号整数'n'将具有以下最后的k个数字:一个后跟(k-1)个零:100 ... 0注意k可以是1,在这种情况下没有零.

(n - 1)将以这种格式结束:零后跟(k-1)1:011 ... 1

因此,n&(n-1)将以'k'零结束:100 ... 0和011 ... 1 = 000 ... 0

因此n&(n-1)将消除最右边的'1'.每次迭代都会基本上删除最右边的'1'数字,因此你可以计算1的数字.