公式 x & (x - 1) 是如何计算的？

Question

来自黑客的喜悦：第二版：

---

这里的公式看起来有点尴尬。当 x 小于 1 时，如何从 1 向量（大概是 0x1111 1111）中减去某个 x 向量？ （例如：（如示例中给出的）0x0101 1000 - 0x0000 0000对我来说没有任何意义）前一个数字比第一个数字小，并且单词也不存储有符号向量。这是与 RISC 特定相关的东西吗？

---

如本书注释部分所指定。粗体字母对应于单词向量，如 x = 00000000。粗体字母与浅色字体 1 不同。如粗体 1 = 11111111，它是一个 8 位单词。

---

Edit2： 特别感谢 Paul Hankin 找出此处使用的非常规符号。粗体字表示 32 位大小的字，即 [00000001]，浅色字 1 表示数字 1，如 C 中所示。

Answer 1

减1

由于我们对十进制比二进制更熟悉，因此有时了解十进制会发生什么会有所帮助。

小数减 1 会发生什么？以

1786000 - 1 = 1785999

为例。

如果用十进制正数

1

减去

x

：

• x

  右边的所有零都变成

  9

  ;

• x

  最右边的非零数字减1；
• 其他数字不受影响。

现在，在二进制中，它的工作原理完全相同，只是我们只有

0 1

而不是

0 123456789

。

如果用二进制数

1

减去

x

：

• x

  右边的所有零都变成

  1

  ；

• x

  最右边的非零位变为

  0

  ；
• 其他位不受影响。

负数呢？令人高兴的是，使用 2 的补码表示时，负数的表现与正数完全相同。事实上，当查看

x

的位时，您可以从

1

中减去

x

，而不需要知道

x

是有符号整型还是无符号整型。

x & (x-1)

让我们从一个例子开始：

x = 01011000

。我们可以按照我刚才解释的方式减去 1：

x   = 01011000
x-1 = 01010111

现在按位与运算

x & (x-1)

的结果是什么？我们取每列中的两位；如果都是1，就写1；如果其中至少有一个为 0，则写 0。

x       = 01011000
x-1     = 01010111
x&(x-1) = 01010000

发生什么事了？

• x

  右侧的所有零保持为零；

• x

  最右边的1变成0，因为

  x-1

  ；
• 所有其他位不受影响，因为它们在

  x

  和

  x-1

  中是相同的。

结论：我们已将

x

最右边的 1 归零，并且所有其他位不受影响。

Answer 2

让我们看看

x-1

做了什么。 假设

x

是一个值

'???? 1000

（？是 0 或 1）

=> x-1 = ???? 0111

=> x & (x-1) = ???? 0000

无论最右边的1放在

x

内的哪个位置，都非常相似。

---

要求的示例：

x=00001111

=> x-1=00001110

=> x & (x-1) = 00001110

P.s.

x-1 = 00001110 - 00000001 (<=> 00001110 + 11111111)

Answer 3

根据用于计算给定数字中设置位的Brian Kernighan 算法，从数字x中减去1将反转其最右边设置位中的所有位。

让，

x = 14

，二进制表示为

1110

。 这里，从右数第 2 位是最右边的设置位。

x - 1 = 13

，二进制表示为

1101

。 可以清楚地观察到，从右数第 2 位开始的位被反转。

现在，如果我们对这两个数字进行按位 AND 运算， 即 x & (x-1) 我们将从数字 x 最右边设置的位中取消设置。看看下面的例子，

    1 1 1 0      (14)      
&   1 1 0 1      (13)

    1 1 0 0      (12)

---

如果数字 x 原本是 2 的幂，那么与 (x-1) 进行按位 AND 将得到 0。例如，

    1 0 0 0      (8)      
&   0 1 1 1      (7)

    0 0 0 0      (0)

这是因为，数字 x 是 2 的幂，在其二进制表示中仅具有 单个 设置位。

---

类似地，如果我们尝试将数字 x 与数字 (x-1) 的

(~) negation

进行按位 AND 操作，那么它只会 set 结果数字中最右边的位。即 x & [~(x-1)]。检查下面的例子，

x = 14

x - 1 = 13

因此，

~(x-1)

将会是，

    1 1 0 1      (13)      
    0 0 1 0      (~13)

因此，

    1 1 1 0      (14)      
&   0 0 1 0      (~13)

    0 0 1 0      (2)

右起第 2 位是数字 x 的二进制表示形式中最右边的设置位，即 14，是结果数字中唯一的 set 位。另外， 是 2 的幂，因为结果中只有一个设置位。