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

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

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

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

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

Примеры:

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

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

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

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

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

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

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

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

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

Например:

 [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] → (второе дополнение или обычное представление) [0’1312]. При переводе из дополнительного кода в обычное представление результирующее значение является абсолютным.

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

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

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

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

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

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

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

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

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

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

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

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;
}

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

 ,

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

Следующий код на языке Си вычисляет модуль по этой формуле:
int32_t fastabs32(int32_t num)
{
    int32_t mask = (num >> 31);
    return ((num ^ mask) - mask);
}

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

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

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

Недостатки 

 Представление отрицательного числа визуально не читается по обычным правилам, для его восприятия нужен особый навык или дополнительные вычисления для приведения в обычный вид.
 В некоторых представлениях (например, двоично-десятичный код) или их составных частях (например, мантисса числа с плавающей запятой) дополнительное кодирование неудобно.
 Модуль наибольшего числа не равен модулю наименьшего числа. Например, для восьмибитного целого со знаком, максимальное число: 12710 = 011111112, минимальное число: -12810 = 100000002. Соответственно, не для любого числа существует противоположное. Операция изменения знака может потребовать дополнительной проверки.

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

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

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

Литература

Ссылки 

Компьютерная арифметика