дополнительный код two s complement
Прямой, обратный и дополнительный коды двоичного числа
Прямой код двоичного числа
Обратный код двоичного числа
Дополнительный код двоичного числа
Мы знаем, что десятичное число можно представить в двоичном виде. К примеру, десятичное число 100 в двоичном виде будет равно 1100100, или в восьмибитном представлении 0110 0100. А как представить отрицательное десятичное число в двоичном виде и произвести с ним арифметические операции? Для этого и предназначены разные способы представления чисел в двоичном коде.
Сразу отмечу, что положительные числа в двоичном коде вне зависимости от способа представления (прямой, обратный или дополнительный коды) имеют одинаковый вид.
Прямой код
Обратный код
Для неотрицательных чисел обратный код двоичного числа имеет тот же вид, что и запись неотрицательного числа в прямом коде.
Для отрицательных чисел обратный код получается из неотрицательного числа в прямом коде, путем инвертирования всех битов (1 меняем на 0, а 0 меняем на 1).
Для преобразования отрицательного числа записанное в обратном коде в положительное достаточного его проинвертировать.
Арифметические операции с отрицательными числами в обратном коде:
Дополнительный код
В дополнительном коде (как и в прямом и обратном) старший разряд отводится для представления знака числа (знаковый бит).
Арифметические операции с отрицательными числами в дополнительном коде
Вывод:
1. Для арифметических операций сложения и вычитания положительных двоичных чисел наиболее подходит применение прямого кода
2. Для арифметических операций сложения и вычитания отрицательных двоичных чисел наиболее подходит применение дополнительного кода
(36 голосов, оценка: 4,67 из 5)
Дополнительный код (представление числа)
Дополнительный код (дополнение до 2) двоичного числа получается добавлением 1 к младшему значащему разряду его дополнения до 1. [1]
Дополнение до 2 двоичного числа определяется как величина полученная вычитанием числа из наибольшей степени двух (из 2 N для N-битного дополнения до 2).
Содержание
Представление отрицательного числа в дополнительном коде
При записи числа в дополнительном коде старший разряд является знаковым. Если его значение равно 0, то в остальных разрядах записано положительное двоичное число, совпадающее с прямым кодом. Если число, записанное в прямом коде, отрицательное, то все разряды числа инвертируются, а к результату прибавляется 1. К получившемуся числу дописывается старший (знаковый) разряд, равный 1.
Двоичное 8-ми разрядное число со знаком в дополнительном коде может представлять любое целое в диапазоне от −128 до +127. Если старший разряд равен нулю, то наибольшее целое число, которое может быть записано в оставшихся 7 разрядах равно 
, что равно 127.
| Десятичное представление | Код двоичного представления (8 бит) | ||
|---|---|---|---|
| прямой | обратный | дополнительный | |
| 127 | 01111111 | 01111111 | 01111111 |
| 1 | 00000001 | 00000001 | 00000001 |
| 0 | 00000000 | 00000000 | 00000000 |
| -0 | 10000000 | 11111111 | — |
| -1 | 10000001 | 11111110 | 11111111 |
| -2 | 10000010 | 11111101 | 11111110 |
| -3 | 10000011 | 11111100 | 11111101 |
| -4 | 10000100 | 11111011 | 11111100 |
| -5 | 10000101 | 11111010 | 11111011 |
| -6 | 10000110 | 11111001 | 11111010 |
| -7 | 10000111 | 11111000 | 11111001 |
| -8 | 10001000 | 11110111 | 11111000 |
| -9 | 10001001 | 11110110 | 11110111 |
| -10 | 10001010 | 11110101 | 11110110 |
| -11 | 10001011 | 11110100 | 11110101 |
| -127 | 11111111 | 10000000 | 10000001 |
| -128 | — | — | 10000000 |
Дополнительный код для десятичных чисел
Тот же принцип можно использовать и в компьютерном представлении десятичных чисел: для каждого разряда цифра X заменяется на 9−X, и к получившемуся числу добавляется 1. Например, при использовании четырёхзначных чисел −0081 заменяется на 9919 (9919+0081=0000, пятый разряд выбрасывается).
При применении той же идеи к привычной 10-ричной системе счисления получится (например, для гипотетического процессора использующего 10-ричную систему счисления):
| 10-ричная система счисления («обычная» запись) | 10-ричная система счисления, дополнительный код |
|---|---|
| . | . |
| 13 | 0013 |
| 12 | 0012 |
| 11 | 0011 |
| 10 | 0010 |
| 9 | 0009 |
| 8 | 0008 |
| . | . |
| 2 | 0002 |
| 1 | 0001 |
| 0 | 0000 |
| -1 | 9999 |
| -2 | 9998 |
| -3 | 9997 |
| -4 | 9996 |
| . | . |
| -9 | 9991 |
| -10 | 9990 |
| -11 | 9989 |
| -12 | 9988 |
| . | . |
Преобразование в дополнительный код
Преобразование числа из прямого кода в дополнительный осуществляется по следующему алгоритму.
Пример. Преобразуем отрицательное число −5, записанное в прямом коде, в дополнительный. Прямой код числа −5, взятого по модулю:
Инвертируем все разряды числа, получая таким образом обратный код:
Добавим к результату 1
Допишем слева знаковый единичный разряд
Для обратного преобразования используется тот же алгоритм. А именно:
Инвертируем все разряды числа, получая таким образом обратный код:
Добавим к результату 1 и проверим, сложив с дополнительным кодом
p-адические числа
В системе p-адических чисел изменение знака числа осуществляется преобразованием числа в его дополнительный код. Например, если используется 5-ричная система счисления, то число, противоположное 1000. (1) равно 4444. (−1).
Обратный и дополнительный коды двоичных чисел
Пример перевода
x1=10101-[x1]пр=010101
x2=-11101-[x2]пр=111101
x3=0,101-[x3]пр=0,101
x4=-0,111-[x4]пр=1,111
2) Обратный код числа, используется для выполнения арифметических операций вычитания, умножения, деления, через сложение. Обратный код положительного числа совпадает с его прямым кодом, обратный код отрицательного числа формируется по правилам: в знаковом разряде записывается “1”; цифровые значения меняются на противоположные.
3) Дополнительный код числа, имеет такое же назначение, как и обратный код числа. Формируется по следующим правилам: положительные числа в дополнительном коде выглядят также как и в обратном и в прямом коде, т.е. не изменяются. Отрицательные числа кодируются следующим образом: к обратному коду отрицательного числа (к младшему разряду) добавляется 1, по правилу двоичной арифметики.
Пример перевода
x1=10101-[x1]доп=010101
x2=-11101-[x2]обр=100010+1-[x2]доп=100011
x3=0,101-[x3]доп=0,101
x4=-0,111-[x4]обр=1,000+1-[x4]доп=1,001
Для выявления ошибок при выполнении арифметических операций используются также модифицированные коды: модифицированный прямой; модифицированный обратный; модифицированный дополнительный, для которых под код знака числа отводится два разряда, т.е. “+”=00; ”-”=11. Если в результате выполнения операции в знаковом разряде появляется комбинация 10 или 01 то для машины это признак ошибки, если 00 или 11 то результат верный.
Прямой, дополнительный и обратный коды
Прямой, дополнительный и обратный код числа (создан по запросу).
Далее идет калькулятор, который переводит введенное положительное или отрицательное целое число в двоичный код, а также выводит обратный код этого числа и его дополнительный код. Под калькулятором, как водится, немного теории.
Обновление: Из комментариев становится ясно, что люди не вполне понимают, что делает этот калькулятор. Точнее, что делал — применял алгоритм вычисления дополнительного кода к любому числу. Люди хотят, чтобы он им просто показывал дополнительный код числа. Ну хорошо — теперь при вводе положительного числа калькулятор показывает представление числа в двоичной форме, ибо для него нет обратного и дополнительного кода, а при вводе отрицательного показывает дополнительный и обратный код.
Прямой, дополнительный и обратный код
Прямой код числа это представление беззнакового двоичного числа. Если речь идет о машинной арифметике, то как правило на представление числа отводится определенное ограниченное число разрядов. Диапазон чисел, который можно представить числом разрядов n равен
Обратный код числа, или дополнение до единицы (one’s complement) это инвертирование прямого кода (поэтому его еще называют инверсный код). То есть все нули заменяются на единицы, а единицы на нули.
Дополнительный код числа, или дополнение до двойки (two’s complement) это обратный код, к младшему значащему разряду которого прибавлена единица
А теперь «зачем, зачем это все?» ©
Для различия положительных и отрицательных чисел выделяют старший разряд числа, который называется знаковым (sign bit)
0 в этом разряде говорит нам о том, что это положительное число, а 1 — отрицательное.
С положительными числами все вроде бы понятно, для их представления можно использовать прямой код
0 — 0000
1 — 0001
7 — 0111
А как представить отрицательные числа?
И это оказалось очень удобно для машинных вычислений — при таком представлении отрицательного числа операции сложения и вычитания можно реализовать одной схемой сложения, при этом очень легко определять переполнение результата (когда для представления получившегося числа не хватает разрядности)
Пара примеров
7-3=4
0111 прямой код 7
1101 дополнительный код 3
0100 результат сложения 4
-1+7=6
1111 дополнительный код 1
0111 прямой код 7
0110 результат сложения 6
Что касается переполнения — оно определяется по двум последним переносам, включая перенос за старший разряд. При этом если переносы 11 или 00, то переполнения не было, а если 01 или 10, то было. При этом, если переполнения не было, то выход за разряды можно игнорировать.
Примеры где показаны переносы и пятый разряд
00111 прямой код 7
00001 прямой код 1
01110 переносы
01000 результат 8 — переполнение
Два последних переноса 01 — переполнение
-7+7=0
00111 прямой код 7
01001 дополнительный код 7
11110 переносы
10000 результат 16 — но пятый разряд можно игнорировать, реальный результат 0
Два последних переноса 11 з перенос в пятый разряд можно отбросить, оставшийся результат, ноль, арифметически корректен.
Опять же проверять на переполнение можно простейшей операцией XOR двух бит переносов.
Вот благодаря таким удобным свойствам дополнительный код это самый распространенный способ представления отрицательных чисел в машинной арифметике.
| Десятичное значение | Дополнительный код комплемент представление |
|---|---|
| 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 затем добавляется к результирующему значению, игнорируя переполнение, которое происходит при взятии дополнения до двух, равного 0.
Например, используя 1 байт (= 8 бит), десятичное число 5 представлено как
Самый старший бит равен 0, поэтому шаблон представляет неотрицательное значение. Чтобы преобразовать в −5 в нотации с дополнением до двух, сначала биты инвертируются, то есть: 0 становится 1, а 1 становится 0:
Дополнение до двух отрицательного числа является соответствующим положительным значением, за исключением одного особого случая. Например, инвертирование битов −5 (см. Выше) дает:
И добавление единицы дает окончательное значение:
Аналогично, два дополнения нуля равны нулю: инвертирование дает все единицы, а добавление единицы изменяет единицы обратно на нули (поскольку переполнение игнорируется).
Дополнение до двух наиболее отрицательного числа, которое может быть представлено (например, единица в качестве самого старшего бита, а все остальные биты равны нулю), является самим собой. Следовательно, существует «лишнее» отрицательное число, для которого дополнение до двух не дает отрицания, см. § Наиболее отрицательное число ниже.
Вычитание из 2 Н
Например, чтобы найти 4-битное представление −5 (нижние индексы обозначают основание представления ):
Следовательно, при N = 4 :
Расчет может быть выполнен полностью по базе 10, преобразовав в конце в базу 2:
Работа от LSB к MSB
В компьютерных схемах этот метод не быстрее, чем метод «дополнить и добавить один»; оба метода требуют последовательной работы справа налево, распространяя логические изменения. Метод дополнения и добавления единицы может быть ускорен стандартной схемой сумматора с упреждающим переносом ; переход от LSB к MSB может быть ускорен аналогичным логическим преобразованием.
Расширение знака
| Десятичный | 7-битная запись | 8-битная запись |
|---|---|---|
| -42 | 1010110 | 1101 0110 |
| 42 | 0101010 | 0010 1010 |
Точно так же, когда число с дополнением до двух сдвигается вправо, должен сохраняться старший значащий бит, который содержит величину и знаковую информацию. Однако при сдвиге влево сдвигается 0. Эти правила сохраняют общую семантику, согласно которой сдвиг влево умножает число на два, а сдвиг вправо делит число на два.
Как сдвиг, так и удвоение точности важны для некоторых алгоритмов умножения. Обратите внимание, что, в отличие от сложения и вычитания, расширение ширины и сдвиг вправо для чисел со знаком и без знака выполняются по-разному.
Самое отрицательное число
За одним исключением, начиная с любого числа в представлении с дополнением до двух, если все биты перевернуты и добавлен 1, получается представление с дополнением до двух отрицательного числа этого числа. Положительный 12 становится отрицательным 12, положительный 5 становится отрицательным 5, ноль становится нулем (+ переполнение) и т. Д.
| −128 | 1000 0000 |
| инвертировать биты | 0111 1111 |
| добавить один | 1000 0000 |
Дополнение до двух минимального числа в диапазоне не приведет к желаемому эффекту отрицания числа. Например, дополнительное двоичное значение −128 в 8-битной системе равно −128. Хотя ожидаемый результат от отрицания −128 равен +128, не существует представления +128 с помощью 8-битной системы дополнения до двух, и поэтому фактически невозможно представить отрицание. Обратите внимание, что два дополнения, являющиеся одним и тем же числом, обнаруживаются как условие переполнения, поскольку произошел перенос в самый старший бит, но не из него.
Наличие самого отрицательного числа может привести к неожиданным ошибкам программирования, когда результат имеет неожиданный знак, или приведет к неожиданному исключению переполнения, или приведет к совершенно странному поведению. Например,
В языках программирования C и C ++ вышеуказанное поведение не определено, и они не только могут возвращать странные результаты, но и компилятор может предположить, что программист обеспечил невозможность выполнения неопределенных вычислений, и сделать выводы из этого предположения. Это позволяет проводить ряд оптимизаций, но также приводит к ряду странных ошибок в таких неопределенных программах.
Самое отрицательное число в дополнении до двух иногда называют «странным числом», потому что это единственное исключение. Хотя число является исключением, это действительное число в обычных системах с дополнением до двух. Все арифметические операции работают с ним и как операнд, и как результат (если не было переполнения).
Почему это работает
Например, с восемью битами байты без знака составляют от 0 до 255. Вычитание 256 из верхней половины (от 128 до 255) дает байты со знаком от –128 до –1.
| Десятичный | Двоичный |
|---|---|
| 127 | 0111 1111 |
| 64 | 0100 0000 |
| 1 | 0000 0001 |
| 0 | 0000 0000 |
| −1 | 1111 1111 |
| −64 | 1100 0000 |
| −127 | 1000 0001 |
| −128 | 1000 0000 |
Пример
Система полезна для упрощения выполнения арифметических операций на компьютерном оборудовании. Добавление 0011 (3.) к 1111 (-1.) Сначала кажется неправильным ответом 10010. Однако оборудование может просто игнорировать самый левый бит, чтобы дать правильный ответ 0010 (2.). По-прежнему должны существовать проверки переполнения, чтобы перехватить такие операции, как суммирование 0100 и 0100.
Таким образом, система позволяет добавлять отрицательные операнды без схемы вычитания или схемы, определяющей знак числа. Более того, эта схема сложения также может выполнять вычитание, взяв дополнение числа до двух (см. Ниже), для чего требуется только дополнительный цикл или собственная схема сумматора. Для этого схема просто работает так, как если бы был крайний левый дополнительный бит 1.
Арифметические операции
Добавление
Добавление чисел в дополнительном коде не требует специальной обработки, даже если операнды имеют противоположные знаки: знак результата определяется автоматически. Например, сложив 15 и −5:
Или вычисление 5-15 = 5 + (−15):
Другими словами, если два левых бита переноса (те, которые находятся в крайнем левом верхнем ряду в этих примерах) равны 1 или оба 0, результат действителен; если два левых бита переноса равны «1 0» или «0 1», произошло переполнение знака. Удобно, что операция XOR над этими двумя битами может быстро определить, существует ли условие переполнения. В качестве примера рассмотрим 4-битное сложение чисел 7 и 3 со знаком:
Вычитание
Компьютеры обычно используют метод дополнений для выполнения вычитания. Использование дополнений для вычитания тесно связано с использованием дополнений для представления отрицательных чисел, поскольку комбинация допускает все знаки операндов и результатов; прямое вычитание работает и с числами с дополнением до двух. Как и в случае сложения, преимущество использования дополнения до двух состоит в том, что исключается проверка знаков операндов для определения необходимости сложения или вычитания. Например, вычитание −5 из 15 на самом деле добавляет 5 к 15, но это скрыто представлением с дополнением до двух:
Переполнение обнаруживается так же, как и при сложении, путем проверки двух крайних левых (наиболее значимых) бита заимствований; произошло переполнение, если они разные.
Что касается сложения, переполнения при вычитании можно избежать (или обнаружить после операции) путем расширения обоих входов с помощью первого знака дополнительным битом.
Умножение
Сравнение (заказ)
Дополнение до двух и 2-адические числа
В классическом HAKMEM, опубликованном лабораторией искусственного интеллекта Массачусетского технологического института в 1972 году, Билл Госпер отметил, что было ли внутреннее представление машины дополнением до двух, можно определить путем суммирования последовательных степеней двойки. В полете фантазии он заметил, что результат выполнения этого алгебраически указывает на то, что «алгебра запускается на машине (вселенной), которая является дополнением до двух».
Преобразование дроби
Например, имея плавающее значение 0,0110 для работы этого метода, не следует рассматривать последний 0 справа. Следовательно, вместо того, чтобы вычислять десятичное значение для 0110, мы вычисляем значение 011, которое равно 3 в десятичной системе (если оставить 0 в конце, результатом будет 6 вместе со знаменателем 2 4 = 16, что сокращается до 3/8). Знаменатель равен 8, что дает окончательный результат 3/8.