- Дополнительный код (представление числа)
-
Дополнительный код (англ. two’s complement, иногда twos-complement) — наиболее распространённый способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел, чем упрощает архитектуру ЭВМ. Дополнительный код отрицательного числа можно получить инвертированием модуля двоичного числа (первое дополнение) и прибавлением к инверсии единицы (второе дополнение), либо вычитанием числа из нуля.
Дополнительный код (дополнение до 2) двоичного числа получается добавлением 1 к младшему значащему разряду его дополнения до 1. [1]
Дополнение до 2 двоичного числа определяется как величина полученная вычитанием числа из наибольшей степени двух (из 2N для 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 ... ... Преобразование в дополнительный код
Преобразование числа из прямого кода в дополнительный осуществляется по следующему алгоритму.
- Если число, записанное в прямом коде, положительное, то к нему дописывается старший (знаковый) разряд, равный 0, и на этом преобразование заканчивается;
- Если число, записанное в прямом коде, отрицательное, то все разряды числа инвертируются, а к результату прибавляется 1. К получившемуся числу дописывается старший (знаковый) разряд, равный 1.
Пример. Преобразуем отрицательное число −5, записанное в прямом коде, в дополнительный. Прямой код числа −5, взятого по модулю:
101
Инвертируем все разряды числа, получая таким образом обратный код:
010
Добавим к результату 1
011
Допишем слева знаковый единичный разряд
1011
Для обратного преобразования используется тот же алгоритм. А именно:
1011
Инвертируем все разряды числа, получая таким образом обратный код:
0100
Добавим к результату 1 и проверим, сложив с дополнительным кодом
0101 + 1011 = 10000, пятый разряд выбрасывается.
p-адические числа
В системе p-адических чисел изменение знака числа осуществляется преобразованием числа в его дополнительный код. Например, если используется 5-ричная система счисления, то число, противоположное 1000... (1) равно 4444.... (−1).
Реализация алгоритма преобразования в обратный код (для 8-битных чисел)
Pascal
if a<0 then a:=((not a) or 128) + 1;
C/C++
if (a < 0) a = ( (~(-a))|128 ) + 1;
Преимущества и недостатки
Преимущества
- Один и тот же регистр может хранить как n-битовое положительное число, так и (n−1)-битовое число со знаком, с общими для обоих форматов операциями сложения, вычитания и левого сдвига.
- Более удобная упаковка чисел в битовые поля.
- Отсутствие числа «минус ноль».
Недостатки
- Дополнительный код неочевиден для новичков.
- В сложных форматах (таких, как плавающая запятая или двоично-десятичный код) большинство преимуществ аннулируются.
- Модуль наибольшего числа не равен модулю наименьшего числа. Пример: знаковое целое 8-битовое. Максимальное число: 12710 == 7F16 == 011111112. Минимальное число: -12810 == 8016,дополнительный код == 100000002,дополнительный код. Соответственно, не для любого числа существует противоположное. Операция изменения знака может потребовать дополнительной проверки.
- Сравнение. В отличие от сложения, числа в дополнительном коде нельзя сравнивать, как беззнаковые, или вычитать без расширения разрядности. Один из методов состоит в сравнении как беззнаковые исходных чисел с инвертированным знаковым битом.
Пример программного преобразования
Если происходит чтение данных из файла или области памяти, где они хранятся в двоичном дополнительном коде (например, файл WAVE), может оказаться необходимым преобразовать байты. Если данные хранятся в 8 битах, необходимо, чтобы значения 128-255 были отрицательными.
C# .NET / C style
byte b1 = 254; //11111110 (бинарное) byte b2 = 121; //01111001 (бинарное) byte c = 1<<(sizeof(byte)*8-1); //2 возводится в степень 7. Результат: 10000000 (бинарное) byte b1Conversion=(c ^ b1) - c; //Результат: -2. А фактически, двоичный дополнительный код. byte b2Conversion=(c ^ b2) - c; //Результат остаётся 121, потому что знаковый разряд - нуль.
См. также
- Обратный код
- Прямой код
- Целый тип
- Алгоритм Бута - специализированный алгоритм умножения для чисел в дополнительном коде
Литература
- Behrooz Parhami 2.3. Complement Representation, 2.4. Two's- and 1's-complement numbers // Computer Arithmetic: Algorithms and Hardware Designs. — New York: Oxford University Press, 2000. — P. 22-27. — 510 p. — ISBN 0-19-512583-5
- Самофалов К.Г., Романкевич А.М., Валуйский В.Н., Каневский Ю.С., Пиневич М.М. Прикладная теория цифровых автоматов. — К.: Вища школа, 1987. — 375 с.
Ссылки
- ↑ К.Г.Жуков "Справочное руководство пользователя Fixed-Point Blockset" 1.2. Понятие прямого, обратного и дополнительного кодов, Определение 3. Архивировано из первоисточника 23 июня 2012.
Категория:- Компьютерная арифметика
Wikimedia Foundation. 2010.