дополнительный код two s complement
Дополнительный код (дополнение до двух)
Чаще всего для представления отрицательных чисел используется код с дополнением до двух (англ. two’s complement). Он же называется обратный дополнительный код.
Алгоритм получения дополнительного кода числа:
если число положительное, то в старший разряд записывается ноль, далее записывается само число;
если число отрицательное, то все биты модуля числа инвертируются, то есть все единицы меняются на нули, а нули — на единицы, к инвертированному числу прибавляется единица, далее к результату дописывается знаковый разряд, равный единице.
| Рис. 4. Нумерация двоичных чисел в представлении c дополнением до двух. |
В качестве примера переведём число −5 в дополнительный восьмибитовый код. Прямой код модуля −5 — 0000101, обратный — 1111010, прибавляем 1, получаем 1111011, приписываем 1 в качестве знакового разряда, в результате получаем 11111011.
Также дополнительный код отрицательного числа 
, хранящегося в 
битах, равен 
. По сути, дополнительный код представляет собой дополнение 
до 
: так как в -разрядной арифметике 
(двоичная запись этого числа состоит из единицы и нулей, а в -разрядную ячейку помещаются только младших разрядов, то есть нулей), то верно равенство 
.
Для получения из дополнительного кода самого числа нужно инвертировать все разряды кода и прибавить к нему единицу. Можно проверить правильность, сложив дополнительный код с самим числом: результат должен быть равен 
. Переведём 11111011 обратно. Инвертируем — 00000100, прибавляем 1, получаем 00000101 — модуль исходного числа −5. Проверим: 11111011 + 00000101 = 100000000.
Можно получить диапазон значений 
.
Достоинства метода:
· возможность заменить арифметическую операцию вычитания операцией сложения и сделать операции сложения одинаковыми для знаковых и беззнаковых типов данных, что существенно упрощает архитектуру процессора и увеличивает его быстродействие;
· нет проблемы двух нулей.
Недостатки: ряд положительных и отрицательных чисел несимметричен, но это не так важно: с помощью дополнительного кода выполнены гораздо более важные вещи, желаемые от способа представления целых чисел.
Арифметические действия над целыми числами
Обратный и дополнительный коды применяются особенно широко, так как они позволяют упростить конструкцию арифметико-логического устройства (АЛУ) компьютера путем замены некоторых арифметических операций сложением.
Обычно десятичные числа при вводе в машину автоматически преобразуются в двоичный код (целые без знака), обратный или дополнительный код (целые со знаком) и в таком виде хранятся, перемещаются и участвуют в операциях. При выводе результатов из машины происходит обратное преобразование в десятичные числа.
Сложение и вычитание
Сложение и вычитание чисел без знака происходит по обычным для позиционных систем счисления алгоритмам.
Ситуации, когда уменьшаемое меньше вычитаемого или когда результат суммы не умещается в k разрядов, считаются ошибочными и должны отслеживаться устройством компьютера. Реакция на такие ошибки может быть различной в разных типах компьютеров.
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим.
Дополнительный код (представление числа)
Дополнительный код (дополнение до 2) двоичного числа получается добавлением 1 к младшему значащему разряду его дополнения до 1. [1]
Дополнение до 2 двоичного числа определяется как величина полученная вычитанием числа из наибольшей степени двух (из 2 N для N-битного дополнения до 2). [2]
Содержание
Представление числа в дополнительном коде
При записи числа в дополнительном коде старший разряд является знаковым. Если его значение равно 0, то в остальных разрядах записано положительное двоичное число, совпадающее с прямым кодом. Если же знаковый разряд равен 1, то в остальных разрядах записано отрицательное двоичное число, преобразованное в дополнительный код. Для получения значения, которое противоположно по знаку, все разряды, включая знаковый, инвертируются, а затем к результату добавляется единица.
| Десятичное представление | Код двоичного представления (8 бит) | |
|---|---|---|
| прямой | дополнительный | |
| 127 | 01111111 | 01111111 |
| 1 | 00000001 | 00000001 |
| 0 | 00000000 | 00000000 |
| -0 | 10000000 | ——— |
| -1 | 10000001 | 11111111 |
| -2 | 10000010 | 11111110 |
| -3 | 10000011 | 11111101 |
| -4 | 10000100 | 11111100 |
| -5 | 10000101 | 11111011 |
| -6 | 10000110 | 11111010 |
| -7 | 10000111 | 11111001 |
| -8 | 10001000 | 11111000 |
| -9 | 10001001 | 11110111 |
| -10 | 10001010 | 11110110 |
| -11 | 10001011 | 11110101 |
| -127 | 11111111 | 10000001 |
| -128 | ——— | 10000000 |
При применении той же идеи к привычной 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 и проверим, сложив с дополнительным кодом
Дополнительный код для десятичных чисел
Тот же принцип можно использовать и в компьютерном представлении десятичных чисел: для каждого разряда цифра X заменяется на 9−X, и к получившемуся числу добавляется 1. Например, при использовании четырёхзначных чисел −0081 заменяется на 9919 (9919+0081=0000, пятый разряд выбрасывается).
Прямой, обратный и дополнительный коды двоичного числа
Прямой код двоичного числа
Обратный код двоичного числа
Дополнительный код двоичного числа
Мы знаем, что десятичное число можно представить в двоичном виде. К примеру, десятичное число 100 в двоичном виде будет равно 1100100, или в восьмибитном представлении 0110 0100. А как представить отрицательное десятичное число в двоичном виде и произвести с ним арифметические операции? Для этого и предназначены разные способы представления чисел в двоичном коде.
Сразу отмечу, что положительные числа в двоичном коде вне зависимости от способа представления (прямой, обратный или дополнительный коды) имеют одинаковый вид.
Прямой код
Обратный код
Для неотрицательных чисел обратный код двоичного числа имеет тот же вид, что и запись неотрицательного числа в прямом коде.
Для отрицательных чисел обратный код получается из неотрицательного числа в прямом коде, путем инвертирования всех битов (1 меняем на 0, а 0 меняем на 1).
Для преобразования отрицательного числа записанное в обратном коде в положительное достаточного его проинвертировать.
Арифметические операции с отрицательными числами в обратном коде:
Дополнительный код
В дополнительном коде (как и в прямом и обратном) старший разряд отводится для представления знака числа (знаковый бит).
Арифметические операции с отрицательными числами в дополнительном коде
Вывод:
1. Для арифметических операций сложения и вычитания положительных двоичных чисел наиболее подходит применение прямого кода
2. Для арифметических операций сложения и вычитания отрицательных двоичных чисел наиболее подходит применение дополнительного кода
(34 голосов, оценка: 4,68 из 5)
| Десятичное значение | Дополнительный код комплемент представление |
|---|---|
| 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.