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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Второе дополнение (англ. Two's complement) двоичного числа определяется как величина, полученная вычитанием числа из наибольшей степени двух (из 2N для N-битного второго дополнения).

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

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

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

Примеры:

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

Дополнительный код в иной системе счисления[править | править код]

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

Преобразования на примере десятичной системы счисления[1][править | править код]

Положительное число[править | править код]

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

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

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

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

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

1000 0101 

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

1111 1010

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

1111 1011

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

1111 1011

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

0000 0100

Добавив к результату 1 получим положительное число 5 в прямом коде:

0101

И проверим, сложив с дополнительным кодом

 0000 0101 + 1111 1011 = 0000 0000, пятый и старше разряды выбрасываются.

p-адические числа[править | править код]

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

Реализация алгоритма преобразования в дополнительный код (для 8-битных чисел)[править | править код]

Pascal[править | править код]

  if (a < 0) then
    a := ((not a) or 128) + 1;

C/C++[править | править код]

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

Преимущества и недостатки[править | править код]

Преимущества[править | править код]

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

Недостатки[править | править код]

  • Представление отрицательного числа визуально не читается по обычным правилам, для его восприятия нужен особый навык или дополнительные вычисления для приведения в обычный вид.
  • В некоторых представлениях (например, двоично-десятичный код) или их составных частях (например, мантисса числа с плавающей запятой) дополнительное кодирование неудобно.
  • Модуль наибольшего числа не равен модулю наименьшего числа. Например, для восьмибитного целого со знаком, максимальное число: 12710 = 011111112, минимальное число: -12810 = 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, потому что знаковый разряд - ноль.

Расширение знака[править | править код]

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

Ссылки[править | править код]

  1. Florida Tech