K&R C 编程语言练习 2-9

Question

我不明白 K&R C 编程语言第 2 章 2.10 中的练习 2-9：

练习2-9。在二进制补码系统中， x &= (x-1) 删除 x 中最右边的 1 位。解释为什么。使用此观察结果编写更快版本的 bitcount 。

位计数函数为：

/* bitcount: count 1 bits in x */

int bitcount(unsigned x)
{
    int b;
    for (b = 0; x != 0; x >>= 1)
        if (x & 01)
            b++;
    return b;
}

该函数在检查最右边的位是否为 bit-1 后将其删除，然后弹出最后一位。

我不明白为什么x&(x-1)要删除最右边的1位？例如，假设 x 是1010且 x-1 是1001二进制的，并且x&(x-1)是1011，所以最右边的位将在那里并且将是 1，我哪里错了？

另外，练习中提到了补码，这和这个问题有关系吗？

多谢！！！

Answer 1

首先，你需要相信K&R是正确的。其次，你可能对这句话有一些误解。

让我再次为您澄清一下。最右边的1位并不是指最右边的位，而是指二进制形式中最右边的1位。

我们任意假设 x 是 xxxxxxx1000（x 可以是 0 或 1）。那么从右到左，第四位就是“最右边的1位”。在这个认识的基础上，我们继续解决这个问题。

为什么x &=(x-1)可以删除最右边的1位？

在二进制补码系统中，-1 用全 1 位模式表示。

所以x-1实际上是x+(-1)，即xxxxxxx1000+11111111111。棘手的一点来了。

最右1位之前全部0变为1，最右1位变为0，并且有一个进位1到左侧。而这个1会继续向最左边走，导致溢出，同时，所有的'x'位仍然是a，因为'x'+'1'+'1'（进位）导致了'x'位。

那么x&(x-1)就会删除最右边的1位。

希望你现在能明白。

谢谢。