WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

Примеры:

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

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

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

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

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

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

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

0101 

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

1010

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

1011

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

1011

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

0100

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

0101

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

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

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

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

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

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

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

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

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

Если происходит чтение данных из файла или области памяти, где они хранятся в двоичном дополнительном коде (например, файл WAVE), может оказаться необходимым преобразовать байты. Если данные хранятся в 8 битах, необходимо, чтобы значения 128-255 были отрицательными.

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) — единицы.

См. также

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

Литература

• 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. ↑ К.Г.Жуков "Справочное руководство пользователя Fixed-Point Blockset" (неопр.) 1.2. Понятие прямого, обратного и дополнительного кодов, Определение 3. Архивировано 23 июня 2012 года.