Дополнительный код

Дополнительный код (англ. two’s complement, иногда twos-complement) — наиболее распространённый способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел, чем упрощает архитектуру ЭВМ. Дополнительный код отрицательного числа можно получить инвертированием модуля двоичного числа (первое дополнение) и прибавлением к инверсии единицы (второе дополнение), либо вычитанием числа из нуля.

Дополнительный код (дополнение до 2) двоичного числа получается добавлением 1 к младшему значащему разряду его дополнения до 1.

Дополнение до 2 двоичного числа определяется как величина полученная вычитанием числа из наибольшей степени двух (из 2^N для N-битного дополнения до 2).

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

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

Двоичное 8-ми разрядное число со знаком в дополнительном коде может представлять любое целое в диапазоне от −128 до +127. Если старший разряд равен нулю, то наибольшее целое число, которое может быть записано в оставшихся 7 разрядах равно $2^{7}-1$, что равно 127.

Примеры:

Десятичное представление	Код двоичного представления (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
...	...

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

Преобразование числа из прямого кода в дополнительный осуществляется по следующему алгоритму.

1. Если число, записанное в прямом коде, положительное, то к нему дописывается старший (знаковый) разряд, равный 0, и на этом преобразование заканчивается;
2. Если число, записанное в прямом коде, отрицательное, то все разряды числа инвертируются, а к результату прибавляется 1. К получившемуся числу дописывается старший (знаковый) разряд, равный 1.

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

101 

Инвертируем все разряды числа, получая таким образом обратный код:

010

Добавим к результату 1

011

Допишем слева знаковый единичный разряд

1011

Для обратного преобразования используется тот же алгоритм. А именно:

1011

Инвертируем все разряды числа, получая таким образом обратный код:

0100

Добавим к результату 1 и проверим, сложив с дополнительным кодом

 0101 + 1011 = 10000, пятый разряд выбрасывается.

Дополнительный код для десятичных чисел

Тот же принцип можно использовать и в компьютерном представлении десятичных чисел: для каждого разряда цифра X заменяется на 9−X, и к получившемуся числу добавляется 1. Например, при использовании четырёхзначных чисел −0081 заменяется на 9919 (9919+0081=0000, пятый разряд выбрасывается).

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-битовое. Максимальное число: 127₁₀ == 7F₁₆ == 01111111₂. Минимальное число: -128₁₀ == 80_{16,дополнительный код} == 10000000_{2,дополнительный код}. Соответственно, не для любого числа существует противоположное. Операция изменения знака может потребовать дополнительной проверки.

Пример программного преобразования

Если происходит чтение данных из файла или области памяти, где они хранятся в двоичном дополнительном коде (например, файл 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 с.