python - 如何思考 Python 的负数按位运算？

Question

我发现很难想到 Python(和 Python3)的无限精度负数和按位运算。它不是 32 位或 64 位的。左边的 1 可以被认为是“无限多”。它不是很确定，这就是为什么有时很难思考它是如何工作的。

似乎一种可行的方法是:总是让它更多，例如，如果您正在处理具有 67 位的正整数，那么只需考虑它们与具有 96 位或 128 位的负数的运算-少量。这是一种正确的思考方式吗？规范中是否有任何说明其工作原理或应该考虑的内容？ (比如内部实现只考虑正整数，而只把负数当成“左移1位”？)

Answer 1

您应该将它们视为具有无限多个 1 位。在摘要中，two's complement二进制表示有无限多个 1；并不是说可以根据需要添加更多的 1，而是那些 1 已经是数字表示方式的一部分。

那些无限多的位实际上并没有存储在内存中这一事实是一个实现细节，因此当您考虑这一点时，您应该忽略内存的限制，直到您遇到您 是必须编写实现的人。如果您只是想从概念上理解这一点，则无需考虑回退位之类的事情，我认为这不一定有帮助。

---

二进制数表示2的幂之和，例如:

11001₂ = 2⁴ + 2³ + 0 + 0 + 2⁰

数字 -1 由无限的 1 序列表示，向左无限延伸:

...1111₂ = ... + 2³ + 2² + 2¹ + 2⁰

这在无穷级数的通常意义上是无稽之谈，但有充分的理由将结果定义为 -1。最直观吸引人的原因是当您按照加法算法将 1 添加到它时会发生什么:

  ...111111111
+            1
  ――――――――――――
= ...000000000 (result)
  ――――――――――――
  ...11111111  (carry)

在最右边的列中，您有 1 + 1，即 2，或二进制形式的 10₂，因此您写一个 0，然后将一个 1 带到下一列的左边。然后在那一列中有一个 1 加上进位的 1，所以你写 0 并进位另一个 1... 依此类推，无穷无尽。结果在每个位置都有一个 0。因此，...11111₂ 一定表示-1，因为我们按照算法加 1，结果表示为 0。

如果这还不够令人满意，那么...11111₂ 应该被解释为 -1 的表示还有其他原因:

• 无限和 1 + 2 + 4 + 8 + ... 是一个几何级数；常数比 r 的几何级数的公式为 1/(1 - r)。此公式仅在 -1 < r < 1 时适用，但如果我们仍然插入 r = 2，那么我们确实会得到结果 -1。
• 无限总和 1 + 2 + 4 + 8 + ... 实际上 确实 在 2-adic norm 中收敛于 -1 .
• 结果-1也可以通过其他定义得到，包括Euler summation , 和 as noted by Wikipedia任何同时是稳定和线性的求和方法都会将此和与结果 ∞ 或 -1 相关联。

我提到这些也是因为它们暗示某些属性仍然适用于算术；应用通常的加法、减法和乘法“无穷大”算法给出符合算术通常属性(如结合律、交换律和分配律)的合理结果。