K&R C编程语言练习2-9
我不理解K&R C编程语言中的练习2-9，第2章，2.10：
练习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，我哪里错了？
另外，练习中提到了二的补语，这和这个问题有关系吗？
非常感谢！
回答 4
Stack Overflow用户
发布于 2018-10-15 16:29:36
首先，你需要相信K&R是正确的。其次，你可能对单词有一些误解。
让我再为你澄清一遍。最右边的1比特并不意味着最右边的比特，而是最右边的比特，它是二进制形式的1。
让我们任意假设x是xxxxxxx1000(x可以是0或1)。然后从右到左，第四位是“最右边的1位”。在这个理解的基础上，让我们继续研究这个问题。
为什么x &=(x-1)可以删除最右边的1位？
在2的补数系统中，-1用全1位模式表示。
所以x-1实际上是x+(-1)，即xxxxxxx1000+11111111111。这是一个棘手的问题。
在最右边的1位之前，所有的0变成1，最右边的1位变成0，有一个进位1转到左边。同时，所有的“x”位仍然是a，因为“x”+“1”+“1”(进位)导致“x”位。
然后x& (x-1)将删除最右边的1位。
希望你现在能理解它。
谢谢。
Stack Overflow用户
发布于 2019-04-03 14:58:44
这里有一个简单的方法来解释它。让我们任意假设数字Y是xxxxxxx1000 (x可以是0或1)。
xxxxxxx1000 -1= xxxxxxx0111
xxxxxxx1000 & xxxxxxx0111 = xxxxxxx0000 (请看，“最右边的1”已经消失了。)
因此，在Y变为0之前Y &= (Y-1)的重复次数将是Y中1的总数。
Stack Overflow用户
发布于 2017-12-02 17:59:33
为什么x & (x-1)要删除最右边的顺序位？试着看看：
如果最右边的位是1，则x具有a...b1的二进制表示，并且x-1是a...b0，因此逐位and将得到a...b1，因为and保持公共位不变，而1 & 0是0
Else x具有a...b10...0的二进制表示；x-1为a...b01...1，出于与上述相同的原因，x & (x-1)将再次为a...b00...0，以清除最右边的order位。
因此，不需要扫描所有位来查找哪个是0，哪个是1，您只需迭代操作x = x & (x-1)，直到x为0:步数将是1位的数量。它比朴素的实现更有效，因为从统计上讲，您将使用一半的步骤。
代码示例：
int bitcount(unsigned int x) {
int nb = 0;
while (x != 0) {
x &= x-1;
nb++
}
return nb;
}https://stackoverflow.com/questions/47606354
复制相似问题
腾讯云开发者
