Сумма степеней 2 в одном дополнении

Question

Все слышали эту шутку Билла Госпера:

Миф о том, что любой данный язык программирования является машинно-независимым, легко разрушается путем вычисления суммы степеней 2.

• Если результат зацикливается с периодом = 1 со знаком +, вы находитесь на машине со знаком.
• Если результат зацикливается с периодом = 1 на -1, вы находитесь на машине с двумя дополнениями.
• Если результат зацикливается с периодом> 1, включая начало, вы находитесь на машине с одним дополнением.
• Если результат зацикливается с периодом> 1, не считая начала, ваш компьютер не является двоичным - шаблон должен указывать вам базу.
• Если у вас не хватает памяти, вы находитесь в строке или системе Bignum.
• Если арифметическое переполнение является фатальной ошибкой, какая-то фашистская свинья с умом только для чтения пытается навязать независимость от машины. Но сама способность ловить переполнение зависит от машины.

По этой стратегии рассмотрим вселенную или, точнее, алгебру:

пусть X = сумма многих степеней двух = ...111111

теперь добавьте X к себе;

Х + Х = ...111110

таким образом, 2X = X - 1, поэтому X = -1

поэтому алгебра запускается на машине (вселенной), которая дополняется двумя.

Я думаю, что понимаю другие части, но я застрял на одной части дополнения. Я рассмотрю простой пример с 3 битами плюс один знаковый бит.

Поведение для bignum и недвоичных архитектур понятно.

Если результат зацикливается с периодом = 1 со знаком +, вы находитесь на машине со знаком.

Когда сила двух переполняется в знаковый бит, он становится отрицательным нулем, поэтому его добавление ничего не меняет. Следующая итерация полностью выпадает, и мы добавляем положительный ноль снова и снова, оставаясь в 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 и положительным значением.

Если результат зацикливается с периодом = 1 на -1, вы находитесь на машине с двумя дополнениями.

Когда степень двух переполняется в знаковый бит, он выдает наименьшее представимое целое число. Добавление этого к

Пример:

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

Если результат зацикливается с периодом> 1, включая начало, вы находитесь на машине с одним дополнением.

Это я не могу понять. Я ожидаю, что это должно пойти:

 ______________________________
|  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 бит падает в конце концов), но тогда как они вычисляются?

Answer 1

Реализация генерации этих "степеней двух" также зависит от машины. Вы предполагали левый сдвиг. Есть еще один способ, который отличается для последних двух машин, а именно добавление текущего к себе.

Сложение с дополнением 8+8 = 1: (или, эквивалентно, -7 + -7)

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