2

在我正在阅读的第 2 章中学习 C“The C 编程语言”的书中。
这本书解释了按位运算，它有一个函数可以显示整数中有多少位。
下面是函数...

int Bitcount(unsigned x){

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

然后给我们一个练习来准确地说明这一点。
“在二进制补码系统中，x &= (x-1) 删除 x 中最右边的 1 位；解释原因。使用此观察来编写更快的 Bitcount 版本”。

问题是我真的无法理解“x &= (x-1)” 是如何工作的？谁可以给我解释一下这个？或将我发送到可以更好地帮助我理解的资源？我一直试图弄清楚这一点，但我真的做不到。

感谢您提供的任何帮助。
另外，如果我的问题有任何问题，这是我的第一篇文章，所以请帮助我把我的问题做得更好。

4

4 回答 4

4

X 和 X-1 不能都将其最右边的位设置为 1，因为在二进制系统中，以 0 和 1 结尾的数字交替出现 - 所以 X & (X-1) 保证是一个最右边的位设置为 0 的数字，即 AND仅当两个项都为真时才计算为真。也许混淆源于 Andrew W 所说的，这里使用了按位与（每个位分别与）？

编辑：现在，正如 Inspired 指出的那样，这只是答案的一部分，因为原始问题指定最右边的 1 位将被重置。由于 Andrew W 已经详细回答了正确的版本，我不会在这里重复他的解释，但我参考他的回答。

于 2013-06-21T15:06:48.573 回答
3

它相当于x = x & (x-1) 这里，& 是按位与，而不是逻辑与。

所以这就是发生的事情：

1) 右边的表达式将首先被计算，该值将存储在 x 中。

2）假设x = 01001011为二进制（不是这种情况，因为将使用超过 8 位来表示 x，但在本例中假设它是）。然后x-1 = 01001010。

3）按位计算和：

01001011 &
01001010 =
01001010

删除了最右边的一位。

现在假设数字没有以 1 位结尾：

说：x = 01001100，(x-1) = 01001011

计算按位和：

01001100 &
01001011 =
01001000

再次删除最右边的 1。

顺便说一句好书。我希望你喜欢它！

于 2013-06-21T15:06:34.380 回答
0

让我们仔细看看 x 中最右边的 1 位：假设x = AAAAAA10000..0，其中 AAAAAA 是任意位。然后x-1 = AAAAAA01111..1。这两个表达式的按位与给出AAAAAA00000..0. 这就是它如何重置最右边的非零位。

于 2013-06-21T15:07:35.310 回答
0

问题是我真的无法理解“x &= (x-1)” 是如何工作的？

二进制数的位置与十进制数相同。当我们增加数字时，我们向左移动一点，当我们减少时，我们从左边借位，就像我们使用小数一样。因此，如果x-01我们从右边借用第一个 1 位，而其他设置为 1 位：

     10101000
   - 00000001
     --------
     10100111

这是这些位的反转，直到第一个 1 位。正如其他人之前所说，~y & y = 0这就是为什么该方法可用于计算 1 位的原因，正如本书提出的那样，使该方法与位移相比更快。

于 2015-07-15T19:40:08.143 回答