stringtranslate.com

Дополнение до двух

Дополнение до двух — наиболее распространенный метод представления знаковых (положительных, отрицательных и нулевых) целых чисел на компьютерах [1] и, в более общем смысле, двоичных значений с фиксированной точкой. Дополнение до двух использует двоичную цифру с наибольшим значением в качестве знака для указания того, является ли двоичное число положительным или отрицательным; когда старший бит равен 1, число подписывается как отрицательное, а когда старший бит равен 0, число подписывается как положительное. В результате неотрицательные числа представляются сами по себе: 6 — это 0110, ноль — это 0000, а -6 — это 1010 (~6 + 1). Обратите внимание, что хотя количество двоичных битов фиксировано на протяжении всего вычисления, в остальном оно произвольно.

В отличие от схемы с дополнением до единиц , схема с дополнением до двух имеет только одно представление для нуля. Более того, арифметические реализации могут использоваться как для целых чисел со знаком, так и без знака [2] и различаются только в ситуациях переполнения целых чисел.

Процедура

Ниже приведена процедура получения дополнения до двух для заданного отрицательного числа в двоичной системе счисления:

Например, чтобы вычислить десятичное число −6 в двоичной системе счисления из числа 6 :

Чтобы убедиться, что 1010 действительно имеет значение −6 , сложите значения мест вместе, но вычтите значение знака из окончательного расчета. Поскольку наиболее значимым значением является значение знака, его необходимо вычесть, чтобы получить правильный результат: 1010 = ( 1 ×2 3 ) + ( 0 ×2 2 ) + ( 1 ×2 1 ) + ( 0 ×2 0 ) = 1 ×−8 + 0 + 1 ×2 + 0 = −6.

Обратите внимание, что шаги 2 и 3 вместе являются допустимым методом вычисления аддитивной инверсии любого (положительного или отрицательного) целого числа , где и вход, и выход находятся в формате дополнения до двух. Альтернативой вычислению является использование вычитания . Ниже см. вычитание целых чисел в формате дополнения до двух.

Теория

Дополнение до двух является примером дополнения до основания . «Два» в названии относится к термину, который, будучи полностью развернутым в N -битной системе, на самом деле является «два в степени N» - 2 N (единственный случай, когда в этом термине будет получено точно «два», это N = 1 , то есть для 1-битной системы, но они не имеют емкости как для знака, так и для нуля), и только этот полный термин вычисляется относительно дополнения . Таким образом, точное определение дополнения до двух N -битного числа является дополнением этого числа относительно 2 N .

Определяющее свойство быть дополнением к числу относительно 2 N заключается просто в том, что суммирование этого числа с исходным дает 2 N. Например, используя двоичную систему счисления с числами до трех бит (то есть N = 3 и 2 N = 2 3 = 8 = 1000 2 , где « 2 » указывает на двоичное представление), дополнение до двух для числа 3 ( 011 2 ) равно 5 ( 101 2 ), поскольку при суммировании с исходным числом оно дает 2 3 = 1000 2 = 011 2 + 101 2 . Там, где это соответствие используется для представления отрицательных чисел, это фактически означает, используя аналогию с десятичными цифрами и числовым пространством, допускающим только восемь неотрицательных чисел от 0 до 7, разделение числового пространства на два набора: первые четыре из чисел 0 1 2 3 остаются теми же, в то время как оставшиеся четыре кодируют отрицательные числа, сохраняя их растущий порядок, таким образом, 4 кодирует -4, 5 кодирует -3, 6 кодирует -2 и 7 кодирует -1. Однако двоичное представление имеет дополнительную полезность, поскольку старший бит также указывает группу (и знак): он равен 0 для первой группы неотрицательных чисел и 1 для второй группы отрицательных чисел. Таблицы справа иллюстрируют это свойство.

Вычисление двоичного дополнения до двух положительного числа по сути означает вычитание числа из 2 N . Но как можно видеть для трехбитного примера и четырехбитного 1000 2 ( 2 3 ), число 2 N само по себе не будет представлено в системе, ограниченной N битами, так как оно находится прямо за пределами пространства N битов (число, тем не менее, является точкой отсчета «дополнения до двух» в N -битной системе). Из-за этого системы с максимальным количеством N битов должны разбить вычитание на две операции: сначала вычесть из максимального числа в N -битной системе, то есть 2 N -1 (этот термин в двоичной системе на самом деле является простым числом, состоящим из «всех единиц», и вычитание из него можно выполнить просто инвертированием всех битов в числе, также известном как операция побитового НЕ ), а затем добавить единицу. По совпадению, это промежуточное число перед добавлением единицы также используется в информатике как еще один метод представления знаковых чисел и называется дополнением до единицы (так названо потому, что суммирование такого числа с исходным дает «все единицы»).

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

История

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

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

Преобразование из представления в дополнительном коде

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

Значение  w 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 Nx . [a]

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

х = 5 10 поэтому х = 0101 2

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

х * = 2 Нх = 2 4 − 5 10 = 16 10 - 5 10 = 10000 2 − 0101 2 = 1011 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 может быть ускорен аналогичным логическим преобразованием.

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

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

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

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

Наибольшее отрицательное число

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

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

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

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

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

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

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

Учитывая набор всех возможных 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 . [11]

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

Связь с дополнением до двух можно понять, заметив, что 256 = 255 + 1 , а (255 − x ) — это дополнение до единицы числа  x .

Пример

В этом подразделе десятичные числа заканчиваются десятичной точкой «.».

Например, 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.

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

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

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

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

Добавление

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

 0000 1111 (15) + 1111 1011 (−5) =========== 0000 1010 (10)

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

 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 бит для хранения всех возможных значений. [13]

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

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

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

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

// обратное сравнение знакового битаесли A ( n - 1 ) == 0 и B ( n - 1 ) == 1 , то вернуть + 1, иначе если A ( n - 1 ) == 1 и B ( n - 1 ) == 0 , то вернуть - 1 конец // сравнение оставшихся битов                      для i = n - 2 ... 0 сделать если A ( i ) == 0 и B ( i ) == 1 тогда вернуть - 1 иначе если A ( i ) == 1 и B ( i ) == 0 тогда вернуть + 1 конец конец вернуть 0                               

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

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

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

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

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

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

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

Примечания

  1. ^ Для x = 0 имеем 2 N − 0 = 2 N , что эквивалентно 0* = 0 по модулю 2 N (т.е. после ограничения до N младших битов).

Ссылки

  1. ^ Например, «Знаковые целые числа — это двоичные значения в дополнительном коде, которые могут использоваться для представления как положительных, так и отрицательных целых чисел». Раздел 4.2.1 в Руководстве разработчика программного обеспечения для архитектур Intel 64 и IA-32, том 1: Базовая архитектура, ноябрь 2006 г.
  2. ^ Бергель, Александр; Кассу, Дэмиен; Дюкасс, Стефан; Лаваль, Янник (2013). Глубоко в Фаро (PDF) . п. 337.
  3. ^ "Two's Complement" (PDF) . Центр академического успеха Университета Рочестера .
  4. ^ Дэвид Дж. Лилья; Сачин С. Сапатнекар (2005). Проектирование цифровых компьютерных систем с помощью Verilog. Издательство Кембриджского университета.
  5. ^ фон Нейман, Джон (1945), Первый черновик отчета о EDVAC (PDF) , получено 20 февраля 2021 г.
  6. ^ "Математика". Спецификация API. Java Platform SE 7.
  7. ^ Регер, Джон (2013). «Никто не ожидает, что испанская инквизиция или INT_MIN будут разделены на -1». Regehr.org (блог).
  8. ^ ab Seacord, Robert C. (2020). «Убедитесь, что операции над знаковыми целыми числами не приводят к переполнению». Правило INT32-C. wiki.sei.cmu.edu . Стандарт кодирования SEI CERT C.
  9. ^ Аффелдт, Рейнальд и Марти, Николас (2006). Формальная проверка арифметических функций в SmartMIPS Assembly (PDF) (Отчет). Архивировано из оригинала (PDF) 2011-07-22.
  10. ^ Харрис, Дэвид Мани; Харрис, Сара Л. (2007). Цифровое проектирование и архитектура компьютеров. Morgan Kaufmann. стр. 18. ISBN 978-0-08-054706-0– через Google Книги.
  11. ^ "3.9. Дополнение до двух". Глава 3. Представление данных . cs.uwm.edu. 2012-12-03. Архивировано из оригинала 31 октября 2013 г. Получено 2014-06-22 .
  12. ^ Finley, Thomas (апрель 2000). "Two's Complement". Computer Science. Заметки для занятий по CS 104. Ithaca, NY: Cornell University . Получено 22.06.2014 .
  13. ^ Бруно Пайяр. Введение в процессоры цифровых сигналов , разд. 6.4.2. Отчет Génie électrique et informationtique, Университет Шербрука, апрель 2004 г.
  14. ^ Карен Миллер (24 августа 2007 г.). "Умножение с дополнительным кодом". cs.wisc.edu . Архивировано из оригинала 13 февраля 2015 г. . Получено 13 апреля 2015 г. .
  15. ^ Уэйкерли, Джон Ф. (2000). Принципы и практики цифрового дизайна (3-е изд.). Prentice Hall. стр. 47. ISBN 0-13-769191-2.
  16. ^ "Programming Hacks". HAKMEM . ПУНКТ 154 (Gosper). Архивировано из оригинала 24.02.2024.
  17. ^ О суммировании 1 + 2 + 4 + 8 + ··· без обращения к 2-адической метрике см. Hardy, GH (1949). Divergent Series . Clarendon Press. LCC  QA295 .H29 1967.(стр. 7–10)
  18. ^ Вюйемен, Жан (1993). О схемах и числах (PDF) . Париж: Digital Equipment Corp. стр. 19. Получено 29.03.2023 ., Глава 7, особенно 7.3 по умножению.
  19. ^ Анашин, Владимир; Богданов, Андрей; Кижватов, Илья (2007). "ABC Stream Cipher". Российский государственный гуманитарный университет . Получено 24 января 2012 г.

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

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