公式 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仍然为零；
• 最右边的 1x变成 0，因为x-1;
• 所有其他位不受影响，因为它们在x和中是相同的x-1。

结论：我们已将 的最右边的 1 清零x，并且所有其他位不受影响。

Answer 2

让我们看一下 ax-1做了什么。假设x是一个值'???? 1000 （？是 0 或 1）
=> x-1 = ???? 0111
=> x & (x-1) = ???? 0000

无论最右边的 1 放在 中的哪个位置，都非常相似x。

请求的示例：
x=00001111
=> x-1=00001110
=> x & (x-1) = 00001110

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