Sum of powers of 2 in one's complement

Question

Everyone has heard this 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.

I think I understand the other parts, but I'm stuck on the one's complement part. I'll consider a simple example with 3 bits plus one sign bit.

The behaviours for bignum and non-binary architectures are clear.

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

When the power of two overflows into the sign bit, it becomes negative zero, so adding it changes nothing. Next iteration, it falls out completely, and we add positive zero over and over, staying at MAXINT.

Example:

 ______________________________
|  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 |
 ...

This is indeed a loop with period 1 and a positive value.

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

When the power of two overflows into the sign bit, it produces the lowest representable integer. Adding that to

Example:

 ______________________________
|  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 |
 ...

Sure enough, it loops at -1.

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

That, I can't figure out. I expect it should go:

 ______________________________
|  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 |
 ...

I especially don't see how it can loop with period greater than 1. This means that the powers of 2 aren't simply generated by shifts left (otherwise the single 1 bit falls off eventually), but then how are they computed?

Answer 1

The implementation of generating these 'powers of two' is also machine-dependent. You assumed left shift. There's another way that differs for the last two machines, namely adding the current one to itself.

One's-complement addition of 8+8 = 1: (or equivalently, -7 + -7)

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