计算位数：这条线如何工作？ n = n&（n-1）; [英] Counting number of bits: How does this line work ? n=n&(n-1);

问题描述

我需要对这条特定行的工作方式进行一些解释。

我知道此函数会计算1的位数，但是该行究竟能清除最右边的1位呢？

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;
}

有人可以简短地向我解释一下还是提供一些证明？ p>

Can some explain it to me briefly or give some "proof"?

推荐答案

任何无符号整数'n'将具有以下最后k位数字：一个后跟（k-1）个零：100。 .0
请注意，在这种情况下，k可以为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）将以以下格式结束：零后跟（ k-1）1's：011 ... 1

(n - 1) will end in this format: Zero followed by (k-1) 1's: 011...1

n& （n-1）因此会以 k零结尾：100 ... 0& 011 ... 1 = 000 ... 0

n & (n-1) will therefore end in 'k' zeroes: 100...0 & 011...1 = 000...0

因此n& （n-1）将消除最右边的 1。每次迭代基本上都会删除最右边的 1数字，因此您可以计算1的数字。

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.

这篇关于计算位数：这条线如何工作？ n = n&（n-1）;的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！