Дополнение до двоек - Twos complement

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

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

Трехбитовые целые числа со знаком

Десятичный ценить	Два дополнения представление
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

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

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

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

История

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

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

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

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

Значениеш из N-битовое целое число ${\displaystyle a_{N-1}a_{N-2}\dots a_{0}}$ дается следующей формулой:

${\displaystyle w=-a_{N-1}2^{N-1}+\sum _{i=0}^{N-2}a_{i}2^{i}}$

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

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

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

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

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

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

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

0000 0101₂

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

1111 1010₂

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

1111 1011₂

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

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

0000 0100₂

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

0000 0101₂

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

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

Вычитание из 2^N

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

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

Икс = 5₁₀ следовательно Икс = 0101₂

Следовательно, с N = 4:

Икс* = 2^N − Икс = 2⁴ − 5₁₀ = 16₁₀ - 5₁₀ = 10000₂ − 0101₂ = 1011₂

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

Икс* = 2^N − Икс = 2⁴ − 5₁₀ = 11₁₀ = 1011₂

Работа от 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-битовые двоичные числа как циклическая группа ${\displaystyle \mathbb {Z} /2^{k}}$, который можно представить в виде круга (или правильного двух^k-угольник), а снятие негативов - это отражение, которое фиксирует элементы порядка, разделяющие 2: 0 и противоположную точку, или визуально зенит и надир.

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

• оператор унарного отрицания не может изменять знак ненулевого числа. например, - (- 128) → −128.

• реализация абсолютная величина может вернуть отрицательное число.^[5] например, абс (-128) → -128.

• Точно так же умножение на -1 может не работать должным образом. например, (−128) × (−1) → −128.

• Деление на -1 может вызвать исключение (например, вызванное делением на 0).^[6] Даже вычисление остатка (или по модулю) по -1 может вызвать это исключение.^[7] например, (−128) ÷ (−1) → сбой, (−128)% (−1) → сбой.

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

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

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

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

Например, для восьми битов беззнаковые байты составляют от 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 в десятичном.^[11]

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

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

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

Добавление

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

  11111 111 (перенос) 0000 1111 (15) + 1111 1011 (−5) =========== 0000 1010 (10)

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

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

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

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

В этом случае два крайних левых (MSB) бита переноса равны «01», что означает, что произошло переполнение сложения с дополнением до двух. То есть 1010₂ = 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-битовые числа требует 2N биты, содержащие все возможные значения.^[12]

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

     00000110 (6) * 11111011 (−5) ============ 110 1100 00000 110000 1100000 11000000 x10000000 + xx00000000 ============ xx11100010

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

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

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

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

Сравнение часто реализуется с фиктивным вычитанием, когда флаги в регистр статуса проверяются, но основной результат игнорируется. В нулевой флаг указывает, равны ли два сравниваемых значения. Если эксклюзивный или знак и переполнение flags равен 1, результат вычитания был меньше нуля, иначе результат был равен нулю или больше. Эти проверки часто реализуются в компьютерах в условная ветвь инструкции.

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

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

// обратное сравнение знакового битаесли А(п-1) == 0 и B(п-1) == 1 тогда    р := +1    переменаеще если А(п-1) == 1 и B(п-1) == 0 тогда    р := -1    переменаконец // сравнение оставшихся битза я = п-2...0 делать    если А(я) == 0 и B(я) == 1 тогда        р := -1        перемена    еще если А(я) == 1 и B(я) == 0 тогда        р := +1        перемена    конецконец р := 0

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

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

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

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

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

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

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

• Алгоритм деления, включая восстанавливающее и невосстанавливающее деление в представлениях с дополнением до двух
• Смещение двоичное
• p-адическое число
• Метод дополнений, обобщение на другие системы счисления, используемые в механических калькуляторах

Рекомендации

1. Например. «Целые числа со знаком - это двоичные значения с дополнением до двух, которые могут использоваться для представления как положительных, так и отрицательных целочисленных значений», Раздел 4.2.1 в Руководстве разработчика программного обеспечения для архитектур Intel 64 и IA-32, Том 1: Базовая архитектура, ноябрь 2006 г.
2. Дэвид Дж. Лилья и Сачин С. Сапатнекар, Проектирование цифровых компьютерных систем с помощью Verilog, Издательство Кембриджского университета, 2005 г. онлайн
3. фон Нейман, Джон (1945), Первый проект отчета о EDVAC (PDF), получено 20 февраля, 2015
4. За Икс = 0 у нас есть 2^N − 0 = 2^N, что эквивалентно 0* = 0 по модулю 2^N (т.е. после ограничения N младшие значащие биты).
5. "Математика". Спецификация API Java Platform SE 7.
6. Регер, Джон (2013). «Никто не ожидает, что испанская инквизиция или INT_MIN разделятся на -1». Regehr.org (блог).
7. Сикорд, Роберт С. (2020). «Правило INT32-C. Убедитесь, что операции с целыми числами со знаком не приводят к переполнению». wiki.sei.cmu.edu. Стандарт кодирования SEI CERT C.
8. Аффельд, Рейнальд и Марти, Николас. «Формальная проверка арифметических функций в сборке SmartMIPS» (PDF). Архивировано из оригинал (PDF) на 22.07.2011.
9. Харрис, Дэвид; Харрис, Дэвид Мани; Харрис, Сара Л. (2007). «Странное двоичное число». Цифровой дизайн и компьютерная архитектура. п. 18 - через Google Книги.
10. «3.9. Дополнение до двух». Глава 3. Представление данных. cs.uwm.edu. 2012-12-03. Получено 2014-06-22.
11. Финли, Томас (апрель 2000 г.). "Два дополнения". Информатика. Заметки о классе для CS 104. Итака, штат Нью-Йорк: Корнельский университет. Получено 2014-06-22.
12. Бруно Пайяр. Введение в цифровые сигнальные процессоры, Разд. 6.4.2. Génie électrique et informatique Report, Université de Sherbrooke, апрель 2004 г.
13. Карен Миллер (24 августа 2007 г.). "Умножение дополнения до двух". cs.wisc.edu. Архивировано из оригинал 13 февраля 2015 г.. Получено 13 апреля, 2015.
14. Вакерли, Джон Ф. (2000). Принципы и методы цифрового дизайна (3-е изд.). Прентис Холл. п. 47. ISBN  0-13-769191-2.
15. Hakmem - Хаки для программирования - Проект, еще не проверенный
16. О суммировании 1 + 2 + 4 + 8 + ··· без обращения к 2-адической метрике см. Харди, Г. (1949). Дивергентная серия. Кларендон Пресс. LCC  QA295 .H29 1967. (стр. 7–10)
17. Vuillemin, Жан (1993). О схемах и цифрах (PDF). Париж: Digital Equipment Corp. п. 19. Получено 2012-01-24.Глава 7, особенно 7.3 для умножения.
18. Анашин, Владимир; Богданов Андрей; Кижватов, Илья (2007). "ABC Stream Cipher". Российский государственный гуманитарный университет. Получено 24 января 2012.

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

• Объяснение дополнения до двух (Томас Финли, 2000)

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

внешняя ссылка

• Симулятор JavaScript с множителем массива с дополнением до двух