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

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

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

История

То, что отрицательные числа в дополнительном коде можно складывать на сумматоре, было известно ещё во времена Паскаля, который и применил это свойство в своей суммирующей машине "Паскалина".

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

При записи числа в дополнительном коде старший разряд является знаковым. Если значение старшего разряда равно 0, то это значит, что в остальных разрядах записано положительное двоичное число, совпадающее с прямым кодом.

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

Примеры:

Десятичное представление	Двоичное представление (8 бит), код:
	прямой	обратный	дополнительный
127	0111 1111	0111 1111	0111 1111
1	0000 0001	0000 0001	0000 0001
0	0000 0000	0000 0000	0000 0000
−0	1000 0000	1111 1111	—
−1	1000 0001	1111 1110	1111 1111
−2	1000 0010	1111 1101	1111 1110
−3	1000 0011	1111 1100	1111 1101
−4	1000 0100	1111 1011	1111 1100
−5	1000 0101	1111 1010	1111 1011
−6	1000 0110	1111 1001	1111 1010
−7	1000 0111	1111 1000	1111 1001
−8	1000 1000	1111 0111	1111 1000
−9	1000 1001	1111 0110	1111 0111
−10	1000 1010	1111 0101	1111 0110
−11	1000 1011	1111 0100	1111 0101
−127	1111 1111	1000 0000	1000 0001
−128	—	—	1000 0000

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

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

Преобразования на примере десятичной системы счисления

Положительное число

Изменение значений текущих разрядов числа не производится, но дописывается знаковый старший разряд, значение которого равно 0. Например число [+12'345] будет иметь следующее представление - [012'345]

Отрицательное число

Дописываем знаковый старший разряд, равный большей цифре данной системы счисления, в нашем случае - это 9, а также изменяем остальные разряды по определённому правилу; пусть значение цифры каждого разряда будет представлено переменной $x$, кроме знакового, тогда представим следующий алгоритм действий:

1. Присвоим переменной $x$ новое значение, равное выражению $9-x$ (процесс получения обратного кода) - например отрицательное число [-12345] в прямом коде от старшего к младшему разряду будет иметь вид [9'12345], где $9$ - знаковая цифра, а в обратном представлении кода будет иметь следующий вид - [9'87654].
2. К результирующему числу прибавим $1$, так число [9'87654] (первое дополнение) будет иметь вид [987'655] (доп. код).
3. Если возникла ситуация переноса разряда, в результате которого образовался новый разряд, то его (старший разряд) опускаем, а результирующее число считаем положительным. Результирующее положительное число будет одинаково представлено, как в прямом, так и в дополнительном коде. Например, имея возможность представить в таком виде отрицательный и положительный нуль, разберём их перевод в дополнительный код (1 знаковый и 4 дополнительных разряда):
   • [+0] в прямом коде [0'0000]. Первое и второе дополнения равны [0'0000].
   • [-0] в прямом коде [9'0000]. Первое дополнение - [9'9999]. При получении второго дополнения старший разряд числа [(1)0'0000] опускаем и получаем результирующее значение [0'0000], как у числа [+0].

Идея представления десятичного (как и любого другого) числа в дополнительном коде, идентична правилам для двоичной системы счисления и может использоваться в гипотетическом процессоре:

Привычное представление	Прямой код	Первое дополнение	Второе дополнение
...	...	...	...
+13	0'0013	0'0013	0'0013
+12	0'0012	0'0012	0'0012
+11	0'0011	0'0011	0'0011
+10	0'0010	0'0010	0'0010
+9	0'0009	0'0009	0'0009
+8	0'0008	0'0008	0'0008
...	...	...	...
+2	0'0002	0'0002	0'0002
+1	0'0001	0'0001	0'0001
+0	0'0000	0'0000	0'0000
-0	9'0000	9'9999	0'0000
-1	9'0001	9'9998	9'9999
-2	9'0002	9'9997	9'9998
-3	9'0003	9'9996	9'9997
-4	9'0004	9'9995	9'9996
...	...	...	...
-9	9'0009	9'9990	9'9991
-10	9'0010	9'9989	9'9990
-11	9'0011	9'9988	9'9989
-12	9'0012	9'9987	9'9988
-13	9'0013	9'9986	9'9987

Арифметика в дополнительном коде

Сложение и вычитание

Оба числа представляются в дополнительном коде. Дополнительный код обоих чисел имеет одинаковое количество разрядов. В данном представлении числа складываются.

Знаки разные: Если в процессе сложения образуется выходящий за пределы первоначальных чисел разряд, то он опускается. Результирующее значение считается положительным, где прямой и дополнительный коды являются идентичными. Иначе — отрицательным в виде дополнительного кода.

Например:

• [1234] + [-78] → [0’1234] + [9’9922] = [(1)0’1156] = [1156].
• [-1234] + [78] → [9’8766] + [0’0078] = [9’8844] = [-1156].

Знаки одинаковые:

• Положительные числа. Разряд не опускается, результат положительный.
• Отрицательные числа. Разряд опускается, результат отрицательный в дополнительном коде.

Например:

• [1234] + [78] → [0’1234] + [0’0078] = [0’1312] = [1312].
• [-1234] + [-78] → [9’8766] + [9’9922] = [(1)9’8688] → (первое дополнение) [0’1311] → (второе дополнение или обычное представление) [-1312]. При переводе из дополнительного кода в обычное представление результирующее значение является абсолютным.

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

Из прямого в дополнительный код

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

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

Для примера преобразуем отрицательное число $-5$, записанное в прямом коде, в дополнительный код.

Прямой код отрицательного числа $-5$:
1000 0101

• Инвертируем все разряды числа, кроме знакового, получая таким образом обратный код (первое дополнение) отрицательного числа $-5$:
  1111 1010
• Добавим к результату $1$, получая таким образом дополнительный код (второе дополнение) отрицательного числа $-5$:
  1111 1011

Изменение знака числа

Для преобразования отрицательного числа $-5$, записанного в дополнительном коде, в положительное число $5$, записанное в прямом коде, используется похожий алгоритм:

• Инвертируем все разряды отрицательного числа $-5$, получая таким образом положительное число 4 в прямом коде:
  0000 0100
• Добавив к результату $1$ получим положительное число $5$ в прямом коде:
  0000 0101

И проверим, сложив получившееся записи $5$ и $-5$:
0000 0101 + 1111 1011 = 0000 0000 (пятый и старше разряды выбрасываются)

p-адические числа

В системе p-адических чисел изменение знака числа осуществляется преобразованием числа в его дополнительный код. Например, если используется 5-ричная система счисления, то число, противоположное 0001₅ (1₁₀), равно 4444₅ (−1₁₀).

Реализация алгоритма нахождения модуля для дополнительного кода

TurboBasic

DEF FN TwosComplAbs%(a%)
    IF a% < 0 THEN a% = NOT(a% - 1)
    FN TwosComplAbs% = a%
END DEF

Pascal

function TwosComplAbs(a: integer): integer;
begin
    if (a < 0) then TwosComplAbs := (not a) + 1
    else TwosComplAbs := a;
end;

C/C++

int twos_compl_abs(int a) {
    if (a < 0) a = (~a) + 1;
    return a;
}

Реализация без ветвления

С помощью следующей формулы можно вычислить модуль числа без ветвления:

$|a|=(a\ {\text{xor}}\ (a\ {\text{shr}}\ (n-1)))-(a\ {\text{shr}}\ (n-1))$,

где: ${\text{xor}}$ — Операция исключающего "или";
${\text{shr}}$ — Арифметический сдвиг вправо;
$n$ — Количество двоичных разрядов

Следующий код на языке Си вычисляет модуль по этой формуле:

int32_t fastabs32(int32_t num)
{
    int32_t mask = (num >> 31);
    return ((num ^ mask) - mask);
}

Преимущества и недостатки

Преимущества

• Общие инструкции (процессора) для сложения, вычитания и левого сдвига для знаковых и беззнаковых чисел (различия только в арифметических флагах, которые нужно проверять для контроля переполнения в результате).
• Отсутствие числа «минус ноль».

Недостатки

• Представление отрицательного числа визуально не читается по обычным правилам, для его восприятия нужен особый навык или дополнительные вычисления для приведения в обычный вид.
• В некоторых представлениях (например, двоично-десятичный код) или их составных частях (например, мантисса числа с плавающей запятой) дополнительное кодирование неудобно.
• Модуль наибольшего числа не равен модулю наименьшего числа. Например, для восьмибитного целого со знаком, максимальное число: 127₁₀ = 01111111₂, минимальное число: -128₁₀ = 10000000₂. Соответственно, не для любого числа существует противоположное. Операция изменения знака может потребовать дополнительной проверки.

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

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

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

Расширение знака (англ. sign extension^[en]) — операция над двоичным числом, которая позволяет увеличить разрядность числа с сохранением знака и значения. Выполняется добавлением цифр со стороны старшего значащего разряда. Если число положительное (старший разряд равен 0), то добавляются нули, если отрицательное (старший разряд равен 1) — единицы.

Пример

Примечание: Добавленные цифры подчёркнуты

Десятичное число	Двоичное число (8 разрядов)	Двоичное число (16 разрядов)
10	0000 1010	0000 0000 0000 1010
−15	1111 0001	1111 1111 1111 0001

См. также

• Обратный код
• Прямой код
• Целый тип
• Алгоритм Бута — специализированный алгоритм умножения для чисел в дополнительном коде

Литература

• 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 с.