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

Question

我不明白练习 2-9，用 K&R C 编程语言， 第 2 章，2.10:

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

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 位。

希望你现在能理解。

谢谢。