Дополнение до двух - Two's complement

Дополнение до двух - это математическая операция над двоичными числами , которая является примером дополнения по основанию системы счисления . Он используется в вычислениях как метод представления числа со знаком .

Дополнение до двух N -битного числа определяется как его дополнение по отношению к 2 N ; сумма числа и его дополнения до двух является 2 N . Например, для трехбитового числа 010 2 дополнение до двух равно 110 2 , потому что 010 2 + 110 2 = 1000 2 = 8 10, что равно 2 3 . Дополнение до двух вычисляется путем инвертирования битов и добавления единицы.

Трехбитовые целые числа со знаком
Десятичное
значение
Дополнительный код комплемент
представление
0 000
1 001
2 010
3 011
−4 100
−3 101
−2 110
−1 111
Восьмибитовые целые числа со знаком
Десятичное
значение
Дополнительный код комплемент
представление
0 0000 0000
1 0000 0001
2 0000 0010
126 0111 1110
127 0111 1111
−128 1000 0000
−127 1000 0001
−126 1000 0010
−2 1111 1110
−1 1111 1111

Дополнение до двух - это наиболее распространенный метод представления целых чисел со знаком на компьютерах и, в более общем смысле, двоичных значений с фиксированной запятой . В этой схеме, если двоичное число 010 2 кодирует целое число 2 10 со знаком , то его дополнение до двух, 110 2 , кодирует обратное: −2 10 . Другими словами, знак большинства целых чисел (всех, кроме одного) может быть изменен в этой схеме, взяв два дополнения его двоичного представления. Таблицы справа иллюстрируют это свойство.

По сравнению с другими системами представления чисел со знаком ( например, дополнением до единиц ), дополнение до двух имеет то преимущество, что основные арифметические операции сложения , вычитания и умножения идентичны таковым для двоичных чисел без знака (при условии, что входные данные представлены в такое же количество битов, что и на выходе, и любое переполнение сверх этих битов исключается из результата). Это свойство упрощает реализацию системы, особенно для высокоточной арифметики. В отличие от систем дополнения до единиц, дополнение до двух не имеет представления для отрицательного нуля и, следовательно, не страдает от связанных с ним трудностей.

Удобно, что другой способ найти двойное дополнение числа состоит в том, чтобы взять его дополнение на единицы и добавить единицу: сумма числа и его дополнения единиц - это все биты '1', или 2 N - 1 ; и по определению, сумма ряда и его двоек, дополнению 2 N .

История

Метод комплементов давно используется для выполнения вычитания в десятичных добавлении машин и механических вычислителей . Джон фон Нейман предложил использовать двоичное представление с дополнением до двух в своем Первом проекте отчета 1945 года о предложении EDVAC для электронного цифрового компьютера с хранимой программой. EDSAC 1949 года , вдохновленный Первым проектом , использовал представление двоичных чисел с дополнением до двух.

Многие ранние компьютеры, включая CDC 6600 , LINC , PDP-1 и UNIVAC 1107, использовали нотацию дополнения до единиц ; потомки UNIVAC 1107, серии UNIVAC 1100/2200 , продолжали это делать. В научных машинах серии IBM 700/7000 используется запись «знак / величина», за исключением индексных регистров, которые являются дополнением до двух. Комплектация двух первых коммерческих компьютеров включает PDP-5 Digital Equipment Corporation и PDP-6 1963 года . Система System / 360 , представленная в 1964 году IBM , тогда доминирующим игроком в компьютерной индустрии, сделала двоичное представление наиболее широко используемым двоичным представлением в компьютерной индустрии. Первый миникомпьютер, PDP-8, представленный в 1965 году, использует арифметику с дополнением до двух, как и Data General Nova 1969 года , PDP-11 1970 года и почти все последующие миникомпьютеры и микрокомпьютеры.

Преобразование из представления дополнения до двух

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

Значение  ш из N битовых целого числа задаются следующей формулой:

Самый старший бит определяет знак числа и иногда называется битом знака . В отличие от представления знака и величины , бит знака также имеет вес - (2 N  - 1 ), показанный выше. Используя N бит, можно представить все целые числа от - (2 N  - 1 ) до 2 N  - 1 - 1 .

Преобразование в представление дополнения до двух

В нотации дополнения до двух неотрицательное число представлено своим обычным двоичным представлением ; в этом случае старший бит равен 0. Хотя диапазон представленных чисел не такой, как у беззнаковых двоичных чисел. Например, 8-битное число без знака может представлять значения от 0 до 255 (11111111). Однако 8-битное число с дополнением до двух может представлять только положительные целые числа от 0 до 127 (01111111), потому что остальные битовые комбинации со старшим битом как «1» представляют отрицательные целые числа от -1 до -128.

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

Из дополнения

Чтобы получить двойное дополнение отрицательного двоичного числа, биты инвертируются или «переворачиваются» с помощью побитовой операции НЕ ; значение 1 затем добавляется к результирующему значению, игнорируя переполнение, которое происходит при взятии дополнения до двух, равного 0.

Например, используя 1 байт (= 8 бит), десятичное число 5 представлено как

0000 0101 2

Старший бит равен 0, поэтому шаблон представляет неотрицательное значение. Чтобы преобразовать в −5 в нотации с дополнением до двух, сначала биты инвертируются, то есть: 0 становится 1, а 1 становится 0:

1111 1010 2

На данный момент представление - это дополнение до единиц десятичного значения −5. Чтобы получить два дополнения, к результату добавляется 1, что дает:

1111 1011 2

Результатом является двоичное число со знаком, представляющее десятичное значение -5 в форме с дополнением до двух. Самый старший бит - 1, поэтому представленное значение отрицательное.

Дополнение до двух отрицательного числа является соответствующим положительным значением, за исключением одного особого случая. Например, инвертирование бит -5 (см. Выше) дает:

0000 0100 2

И добавление единицы дает окончательное значение:

0000 0101 2

Аналогично, два дополнения нуля равны нулю: инвертирование дает все единицы, а добавление единицы изменяет единицы обратно на нули (поскольку переполнение игнорируется).

Дополнение до двух наиболее отрицательного числа, которое может быть представлено (например, единица в качестве самого старшего бита, а все остальные биты равны нулю), является самим собой. Следовательно, существует «лишнее» отрицательное число, для которого дополнение до двух не дает отрицания, см. § Наиболее отрицательное число ниже.

Вычитание из 2 Н

Сумма числа и его дополнения до единиц представляет собой N -битное слово со всеми 1 битами, которое (при чтении как двоичное число без знака) равно 2 N - 1 . Затем добавить номер к его дополнением до двух результатов в N низших битов , установленных в 0 и бит переноса 1, где последний имеет вес (чтение его в качестве двоичного числа без знака) от 2 N . Следовательно, в беззнаковой двоичной арифметике значение отрицательного числа x * с дополнением до двух для положительного x удовлетворяет равенству x * = 2 N - x .

Например, чтобы найти 4-битное представление −5 (нижние индексы обозначают основание представления ):

x = 5 10, следовательно, x = 0101 2

Следовательно, при N = 4 :

х * = 2 Н - х = 2 4 - 5 10 = 16 10 - 5 10 = 10000 2 - 0101 2 = 1011 2

Расчет может быть выполнен полностью по базе 10, преобразовав в конце в базу 2:

х * = 2 Н - х = 2 4 - 5 10 = 11 10 = 1011 2

Работа от LSB к MSB

Быстрый способ вручную преобразовать двоичное число в его дополнение до двух состоит в том, чтобы начать с наименее значащего бита (LSB) и скопировать все нули, работая от LSB к наиболее значимому биту (MSB), пока не будет достигнута первая 1; затем скопируйте эту 1 и переверните все оставшиеся биты (оставьте MSB равным 1, если исходное число было в знаково-величинном представлении). Этот ярлык позволяет человеку преобразовать число в дополнение до двух без предварительного формирования его дополнения. Например: в представлении с дополнением до двух отрицание «0011 1100» равно «1100 0 100 », где подчеркнутые цифры не изменились в результате операции копирования (в то время как остальные цифры были перевернуты).

В компьютерных схемах этот метод не быстрее, чем метод «дополнить и добавить один»; оба метода требуют последовательной работы справа налево, распространяя логические изменения. Метод дополнения и добавления единицы может быть ускорен стандартной схемой сумматора с упреждающим переносом ; переход от LSB к MSB может быть ускорен аналогичным логическим преобразованием.

Расширение знака

Повторение знаковых битов в 7- и 8-битных целых числах с использованием дополнения до двух
Десятичный 7-битная запись 8-битная запись
−42  1010110 1101 0110
42  0101010 0010 1010

При преобразовании числа с дополнением до двух с определенным количеством битов в одно с большим количеством бит (например, при копировании из 1-байтовой переменной в 2-байтовую переменную) самый старший бит должен повторяться во всех дополнительных битах. . Некоторые процессоры делают это с помощью одной инструкции; на других процессорах необходимо использовать условное выражение, за которым следует код для установки соответствующих битов или байтов.

Точно так же, когда число с дополнением до двух сдвигается вправо, должен сохраняться старший значащий бит, который содержит величину и знаковую информацию. Однако при сдвиге влево сдвигается 0. Эти правила сохраняют общую семантику, согласно которой сдвиг влево умножает число на два, а сдвиг вправо делит число на два.

Как сдвиг, так и удвоение точности важны для некоторых алгоритмов умножения. Обратите внимание, что, в отличие от сложения и вычитания, расширение ширины и сдвиг вправо для чисел со знаком и без знака выполняются по-разному.

Самое отрицательное число

За одним исключением, начиная с любого числа в представлении с дополнением до двух, если все биты перевернуты и добавлен 1, получается представление с дополнением до двух отрицательного числа этого числа. Положительный 12 становится отрицательным 12, положительный 5 становится отрицательным 5, ноль становится нулем (+ переполнение) и т. Д.

Дополнение до -128 до двух дает одно и то же 8-битное двоичное число.
−128 1000 0000
инвертировать биты 0111 1111
добавить один 1000 0000

Дополнение до двух минимального числа в диапазоне не приведет к желаемому эффекту отрицания числа. Например, дополнительное двоичное значение −128 в 8-битной системе равно −128. Хотя ожидаемый результат от отрицания −128 равен +128, не существует представления +128 с помощью 8-битной системы дополнения до двух, и поэтому фактически невозможно представить отрицание. Обратите внимание, что два дополнения, являющиеся одним и тем же числом, обнаруживаются как условие переполнения, поскольку произошел перенос в самый старший бит, но не из него.

Это явление связано с математикой двоичных чисел, а не с деталями их представления в виде дополнения до двух. Математически это дополняет тот факт, что отрицательное значение 0 снова равно 0. Для заданного числа битов k есть четное число двоичных чисел 2 k , принятие отрицательных значений является групповым действием (группы порядка 2) на двоичные числа, и поскольку орбита нуля имеет порядок 1, по крайней мере одно другое число должно иметь орбиту порядка 1, чтобы порядки орбит суммировались до порядка набора. Таким образом, какое-то другое число должно быть инвариантным относительно взятия отрицательных значений (формально по теореме о стабилизаторе орбиты ). Геометрически, можно просмотреть K -разрядного двоичных чисел в качестве циклической группы , которые могут быть визуализированы в виде круга (или правильно регулярный 2 K -угольник), и принимая негативов является отражением, который фиксирует элементы порядка деления 2: 0 и противоположная точка, или визуально зенит и надир.

Наличие самого отрицательного числа может привести к неожиданным ошибкам программирования, когда результат имеет неожиданный знак, или приведет к неожиданному исключению переполнения, или приведет к совершенно странному поведению. Например,

  • оператор унарного отрицания не может менять знак ненулевого числа. например, - (- 128) → −128.
  • Точно так же умножение на -1 может не работать должным образом. например, (−128) × (−1) → −128.
  • Деление на -1 может вызвать исключение (например, вызванное делением на 0). Даже вычисление остатка (или по модулю) по -1 может вызвать это исключение. например, (−128) ÷ (−1) → сбой, (−128)% (−1) → сбой.

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

Самое отрицательное число в дополнении до двух иногда называют «странным числом», потому что это единственное исключение. Хотя это число является исключением, это действительное число в обычных системах с дополнением до двух. Все арифметические операции работают с ним и как операнд, и как результат (если не было переполнения).

Почему это работает

Учитывая набор всех возможных N -битных значений, мы можем назначить нижнюю (по двоичному значению) половину целыми числами от 0 до (2 N  - 1 - 1) включительно, а верхнюю половину равной −2 N  - 1. до −1 включительно. Верхняя половина (опять же, двоичная величина) может использоваться для представления отрицательных целых чисел от -2 N  - 1 до -1, потому что при сложении по модулю 2 N они ведут себя так же, как эти отрицательные целые числа. То есть, поскольку i + j mod 2 N = i + ( j + 2 N ) mod 2 N, любое значение в наборе {  j + k  2 N | k - целое число}  может использоваться вместо  j .

Например, для восьми битов беззнаковые байты составляют от 0 до 255. Вычитание 256 из верхней половины (от 128 до 255) дает подписанные байты от −128 до −1.

Отношения с дополнением до двух реализуется, отметив , что 256 = 255 + 1 , а (255 - х ) представляет собой обратный код из  х .

Некоторые специальные числа на заметку
Десятичный Двоичный
127  0111 1111
64  0100 0000
1   0000 0001
0   0000 0000
−1  1111 1111
−64  1100 0000
−127  1000 0001
−128  1000 0000

Пример

В этом подразделе десятичные числа имеют суффикс с десятичной точкой "".

Например, 8-битное число может представлять только каждое целое число от −128. до 127. включительно, так как (2 8 - 1 = 128.) . −95. по модулю 256. эквивалентно 161. так как

−95. + 256.
= -95. + 255. + 1
= 255. - 95. + 1
= 160. + 1.
= 161.
   1111 1111 255.
 - 0101 1111 - 95.
 =========== =====
   1010 0000 (дополнение) 160.
 + 1 + 1
 =========== =====
   1010 0001 (дополнение до двух) 161.
4-битные целые числа с дополнением до двух
Два дополнения Десятичный
0111 7. 
0110 6. 
0101 5. 
0100 4. 
0011 3. 
0010 2. 
0001 1. 
0000 0. 
1111 −1. 
1110 −2. 
1101 −3. 
1100 −4. 
1011 −5. 
1010 −6. 
1001 −7. 
1000 −8. 

По сути, система представляет отрицательные целые числа, считая в обратном порядке и оборачиваясь вокруг них . Граница между положительными и отрицательными числами произвольна, но по соглашению все отрицательные числа имеют самый левый бит ( самый старший бит ), равный единице. Следовательно, самое положительное 4-битное число - 0111 (7.), а самое отрицательное - 1000 (-8.). Из-за использования самого левого бита в качестве знакового бита абсолютное значение самого отрицательного числа (| -8. | = 8.) слишком велико для представления. Отрицание числа в дополнительном двоичном коде просто: инвертируйте все биты и прибавляйте к результату единицу. Например, отрицая 1111, мы получаем 0000 + 1 = 1 . Следовательно, 1111 в двоичном формате должно представлять -1 в десятичном.

Система полезна для упрощения выполнения арифметических операций на компьютерном оборудовании. Добавление 0011 (3.) к 1111 (-1.) Сначала кажется неправильным ответом 10010. Однако оборудование может просто игнорировать самый левый бит, чтобы дать правильный ответ 0010 (2.). По-прежнему должны существовать проверки переполнения, чтобы перехватить такие операции, как суммирование 0100 и 0100.

Таким образом, система позволяет добавлять отрицательные операнды без схемы вычитания или схемы, определяющей знак числа. Более того, эта схема сложения также может выполнять вычитание, взяв дополнение числа до двух (см. Ниже), для чего требуется только дополнительный цикл или собственная схема сумматора. Для этого схема просто работает так, как если бы был крайний левый дополнительный бит 1.

Арифметические операции

Добавление

Добавление чисел в дополнительном коде не требует специальной обработки, даже если операнды имеют противоположные знаки: знак результата определяется автоматически. Например, сложив 15 и −5:

  11111 111 (нести)
   0000 1111 (15)
 + 1111 1011 (−5)
 ===========
   0000 1010 (10)

Или вычисление 5-15 = 5 + (−15):

          1 (нести)
   0000 0101 (5)
 + 1111 0001 (−15)
 ===========
   1111 0110 (-10)

Этот процесс зависит от ограничения до 8 бит точности; перенос в (несуществующий) 9-й старший значащий бит игнорируется, что дает арифметически правильный результат 10 10 .

Последние два бита строки переноса (чтение справа налево) содержат важную информацию: привело ли вычисление к арифметическому переполнению , слишком большому числу для представления двоичной системы (в данном случае больше 8 бит). Когда эти два последних бита отличаются друг от друга, возникает состояние переполнения. Как упоминалось выше, знак числа кодируется в старшем разряде результата.

Другими словами, если два левых бита переноса (те, которые находятся в крайнем левом верхнем ряду в этих примерах) равны 1 или оба 0, результат действителен; если два левых бита переноса равны «1 0» или «0 1», произошло переполнение знака. Удобно, что операция XOR над этими двумя битами может быстро определить, существует ли условие переполнения. В качестве примера рассмотрим 4-битное сложение чисел 7 и 3 со знаком:

  0111 (переносить)
   0111 (7)
 + 0011 (3)
 ======
   1010 (−6) неверно!

В этом случае два крайних левых (MSB) бита переноса равны «01», что означает, что произошло переполнение сложения с дополнением до двух. То есть 1010 2 = 10 10 выходит за пределы допустимого диапазона от -8 до 7. Результат будет правильным, если рассматривать его как целое число без знака.

В общем, любые два N -битных числа могут быть добавлены без переполнения, сначала расширив их знак до N  + 1 бит, а затем сложив, как указано выше. Результат N  + 1 битов достаточно велик, чтобы представить любую возможную сумму ( N = 5 дополнение до двух может представлять значения в диапазоне от -16 до 15), поэтому переполнение никогда не произойдет. Затем можно, при желании, «усечь» результат обратно до N битов, сохраняя значение тогда и только тогда, когда отброшенный бит является надлежащим знаковым расширением сохраненных битов результата. Это обеспечивает другой метод обнаружения переполнения, который эквивалентен методу сравнения битов переноса, но который может быть проще реализовать в некоторых ситуациях, поскольку он не требует доступа к внутренним компонентам добавления.

Вычитание

Компьютеры обычно используют метод дополнений для выполнения вычитания. Использование дополнений для вычитания тесно связано с использованием дополнений для представления отрицательных чисел, поскольку комбинация допускает все знаки операндов и результатов; прямое вычитание работает и с числами с дополнением до двух. Как и в случае сложения, преимущество использования дополнения до двух состоит в том, что исключается проверка знаков операндов для определения необходимости сложения или вычитания. Например, вычитание −5 из 15 на самом деле добавляет 5 к 15, но это скрыто представлением с дополнением до двух:

  11110 000 (заем)
   0000 1111 (15)
 - 1111 1011 (−5)
 ===========
   0001 0100 (20)

Переполнение обнаруживается так же, как и при сложении, путем проверки двух крайних левых (наиболее значимых) бита заимствований; произошло переполнение, если они разные.

Другой пример - операция вычитания, когда результат отрицательный: 15-35 = -20:

  11100 000 (заем)
   0000 1111 (15)
 - 0010 0011 (35)
 ===========
   1110 1100 (-20)

Что касается сложения, переполнения при вычитании можно избежать (или обнаружить после операции) путем расширения обоих входов с помощью первого знака дополнительным битом.

Умножение

Произведение двух N -битных чисел требует, чтобы 2 N бит содержали все возможные значения.

Если точность двух операндов, использующих дополнение до двух, удваивается перед умножением, прямое умножение (отбрасывание любых лишних битов сверх этой точности) даст правильный результат. Например, возьмем 6 × (−5) = −30 . Во-первых, точность увеличена с четырех до восьми. Затем числа умножаются, отбрасывая биты за восьмым битом (как показано « x »):

     00000110 (6)
 * 11111011 (-5)
 ============
          110
         1100
        00000
       110000
      1100000
     11000000
    х10000000
 + xx00000000
 ============
   xx11100010

Это очень неэффективно; За счет заблаговременного удвоения точности все добавления должны иметь двойную точность, и требуется как минимум вдвое больше частичных произведений, чем для более эффективных алгоритмов, фактически реализованных в компьютерах. Некоторые алгоритмы умножения разработаны для дополнения до двух, особенно алгоритм умножения Бута . Методы умножения знаковых чисел не работают с числами в дополнительном коде без адаптации. Обычно не возникает проблем, когда множимое (многократно добавляемое для образования произведения) отрицательное; проблема заключается в правильной установке начальных битов продукта, когда множитель отрицательный. Распространены два метода адаптации алгоритмов для обработки чисел с дополнением до двух:

  • Сначала проверьте, отрицательный ли множитель. Если это так, инвертируйте ( т. Е. Возьмите дополнение до двух) оба операнда перед умножением. Тогда множитель будет положительным, поэтому алгоритм будет работать. Поскольку оба операнда инвертируются, результат по-прежнему будет иметь правильный знак.
  • Вычтите частичный продукт, полученный из MSB (бит псевдознака), вместо того, чтобы добавлять его, как другие частичные продукты. Этот метод требует, чтобы знаковый бит множимого был расширен на одну позицию, сохраняясь во время сдвига вправо.

В качестве примера второго метода возьмем обычный алгоритм сложения и сдвига для умножения. Вместо смещения частичных продуктов влево, как это делается с карандашом и бумагой, накопленный продукт смещается вправо, во второй регистр, который в конечном итоге будет содержать наименее значимую половину продукта. Поскольку младшие значащие биты не меняются после вычисления, добавления могут иметь одинарную точность и накапливаться в регистре, который в конечном итоге будет содержать старшую половину произведения. В следующем примере, снова при умножении 6 на -5, два регистра и бит расширенного знака разделены знаком "|":

  0 0110 (6) (множимое с расширенным битом знака)
  × 1011 (−5) (множитель)
  = | ==== | ====
  0 | 0110 | 0000 (первое частичное произведение (крайний правый бит равен 1))
  0 | 0011 | 0000 (сдвиг вправо, с сохранением расширенного бита знака)
  0 | 1001 | 0000 (добавить второй частичный продукт (следующий бит равен 1))
  0 | 0100 | 1000 (сдвиг вправо, с сохранением расширенного бита знака)
  0 | 0100 | 1000 (добавьте третий частичный продукт: 0, чтобы без изменений)
  0 | 0010 | 0100 (сдвиг вправо, с сохранением расширенного бита знака)
  1 | 1100 | 0100 (вычтите последнее частичное произведение, поскольку оно из знакового бита)
  1 | 1110 | 0010 (сдвиг вправо, с сохранением расширенного бита знака)
   | 1110 | 0010 (отбросить расширенный знаковый бит, дав окончательный ответ, −30)

Сравнение (заказ)

Сравнение часто осуществляется с помощью фиктивного вычитания, когда проверяются флаги в регистре состояния компьютера , но основной результат игнорируется. Флаг нуль указывает на то, если два значения равны по сравнению. Если знак «исключающее ИЛИ» и флаги переполнения равны 1, результат вычитания был меньше нуля, в противном случае результат был равен нулю или больше. Эти проверки часто реализуются в компьютерах с помощью инструкций условного перехода .

Беззнаковые двоичные числа могут быть упорядочены простым лексикографическим порядком , где битовое значение 0 определяется как меньшее, чем битовое значение 1. Для значений дополнения до двух значение самого значимого бита меняется на противоположное (т. Е. 1 меньше 0).

Следующий алгоритм (для n- битной архитектуры дополнения до двух) устанавливает регистр результатов R в -1, если A <B, в +1, если A> B, и в 0, если A и B равны:

// reversed comparison of the sign bit

if A(n-1) == 0 and B(n-1) == 1 then
    return +1
else if A(n-1) == 1 and B(n-1) == 0 then
    return -1
end
 
// comparison of remaining bits

for i = n-2...0 do
    if A(i) == 0 and B(i) == 1 then
        return -1
    else if A(i) == 1 and B(i) == 0 then
        return +1 
    end
end
 
return 0

Дополнение до двух и 2-адические числа

В классическом HAKMEM, опубликованном лабораторией искусственного интеллекта Массачусетского технологического института в 1972 году, Билл Госпер отметил, что вопрос о том, является ли внутреннее представление машины дополнением до двух, можно определить путем суммирования последовательных степеней двойки. В полете своей фантазии он заметил, что результат выполнения этого алгебраически указывает на то, что «алгебра выполняется на машине (вселенной), которая является дополнением до двух».

Окончательный вывод Госпера не обязательно должен восприниматься всерьез, и он сродни математической шутке . Критический шаг: «... 110 = ... 111 - 1», то есть «2 X = X  - 1», и, следовательно, X  = ... 111 = -1. Это предполагает метод, с помощью которого бесконечная строка единиц считается числом, что требует расширения концепций конечных разрядов в элементарной арифметике. Оно имеет смысл либо как часть записи с дополнением до двух для всех целых чисел, как типичное 2-адическое число , либо даже как одна из обобщенных сумм, определенных для расходящегося ряда действительных чисел 1 + 2 + 4 + 8 + ··. · . Цифровые арифметические схемы, идеализированные для работы с бесконечными (расширяющимися до положительных степеней двойки) битовыми строками, производят 2-адическое сложение и умножение, совместимые с представлением дополнения до двух. Непрерывность двоичных арифметических и поразрядных операций в 2-адической метрике также имеет некоторое применение в криптографии.

Преобразование дроби

Чтобы преобразовать число с дробной частью, например .0101, необходимо преобразовать единицы в десятичные, начиная справа налево, как при обычном преобразовании. В этом примере 0101 равно 5 в десятичной системе счисления. Каждая цифра после числа с плавающей запятой представляет собой дробь, где знаменатель - это множитель 2. Итак, первая цифра - 1/2, вторая - 1/4 и так далее. После расчета десятичного значения, как указано выше, используется только знаменатель LSB (LSB = начиная справа). Конечный результат этого преобразования - 5/16.

Например, имея плавающее значение 0,0110 для работы этого метода, не следует рассматривать последний 0 справа. Следовательно, вместо того, чтобы вычислять десятичное значение для 0110, мы вычисляем значение 011, которое равно 3 в десятичной системе (если оставить 0 в конце, результатом будет 6 вместе со знаменателем 2 4  = 16, что сокращается до 3/8). Знаменатель равен 8, что дает окончательный результат 3/8.

Смотрите также

использованная литература

дальнейшее чтение

  • Корен, Израиль (2002). Компьютерные арифметические алгоритмы . А.К. Петерс. ISBN 1-56881-160-8.
  • Флорес, Иван (1963). Логика компьютерной арифметики . Прентис-Холл.

внешние ссылки