2 的补码的幂和

Sum of powers of 2 in one's complement

大家都听说过joke by Bill Gosper:

The myth that any given programming language is machine independent is easily exploded by computing the sum of powers of 2.

  • If the result loops with period = 1 with sign +, you are on a sign-magnitude machine.
  • If the result loops with period = 1 at -1, you are on a twos-complement machine.
  • If the result loops with period > 1, including the beginning, you are on a ones-complement machine.
  • If the result loops with period > 1, not including the beginning, your machine isn't binary -- the pattern should tell you the base.
  • If you run out of memory, you are on a string or Bignum system.
  • If arithmetic overflow is a fatal error, some fascist pig with a read-only mind is trying to enforce machine independence. But the very ability to trap overflow is machine dependent.

By this strategy, consider the universe, or, more precisely, algebra:

let X = the sum of many powers of two = ...111111

now add X to itself;

X + X = ...111110

thus, 2X = X - 1 so X = -1

therefore algebra is run on a machine (the universe) which is twos-complement.

我想我理解其他部分,但我卡在了补语部分。我将考虑一个包含 3 位加一个符号位的简单示例。

bignum 和非二进制架构的行为很清楚。

If the result loops with period = 1 with sign +, you are on a sign-magnitude machine.

当2的幂溢出到符号位时,它变成负零,所以加上它没有任何改变。下一次迭代,它完全消失了,我们一遍又一遍地添加正零,停留在 MAXINT.

示例:

 ______________________________
|  Power of 2  ||  Accumulator |
| |   ||Decimal|| |   ||Decimal|
|0|001||    +1 ||0|001||    +1 |
|0|010||    +2 ||0|011||    +3 |
|0|100||    +4 ||0|111||    +7 |
|1|000||    -0 ||0|111||    +7 |
|0|000||    +0 ||0|111||    +7 |
|0|000||    +0 ||0|111||    +7 |
 ...

这确实是一个周期为 1 且值为正值的循环。

If the result loops with period = 1 at -1, you are on a twos-complement machine.

当2的幂溢出到符号位时,它产生最低的可表示整数。将其添加到

示例:

 ______________________________
|  Power of 2  ||  Accumulator |
| |   ||Decimal|| |   ||Decimal|
|0|001||    +1 ||0|001||    +1 |
|0|010||    +2 ||0|011||    +3 |
|0|100||    +4 ||0|111||    +7 |
|1|000||    -8 ||1|111||    -1 |
|0|000||    +0 ||1|111||    -1 |
|0|000||    +0 ||1|111||    -1 |
 ...

果然,它在-1循环。

If the result loops with period > 1, including the beginning, you are on a ones-complement machine.

那个,我想不通。我希望它应该:

 ______________________________
|  Power of 2  ||  Accumulator |
| |   ||Decimal|| |   ||Decimal|
|0|001||    +1 ||0|001||    +1 |
|0|010||    +2 ||0|011||    +3 |
|0|100||    +4 ||0|111||    +7 |
|1|000||    -7 ||1|111||    -0 |
|0|000||    +0 ||1|111||    -0 |
|0|000||    +0 ||1|111||    -0 |
 ...

我特别不明白它如何以大于 1 的周期循环。这意味着 2 的幂不是简单地由左移产生的(否则单个 1 位最终会消失),但是如何它们是经过计算的吗?

生成这些 'powers of two' 的实现也取决于机器。你假设左移。最后两台机器还有另一种不同的方法,即将当前机器添加到自身。

8+8 = 1 的补码加法:(或等效地,-7 + -7)

   1000
 + 1000
-------
 1 0000
      1
-------
   0001