Дополнительный код
Дополнительный код (англ. 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 |
Дополнительный код для десятичных чисел
[править | править код]Тот же принцип можно использовать и в компьютерном представлении десятичных чисел: для каждого разряда цифра X заменяется на 9−X, и к получившемуся числу добавляется 1. Например, при использовании четырёхзначных чисел −0081 заменяется на 9919 (9919+0081=0000, пятый разряд выбрасывается).
При применении той же идеи к привычной десятичной системе счисления получится (например, для гипотетического процессора, использующего десятичную систему счисления):
Десятичная система счисления («обычная» запись) |
Десятичная система счисления, дополнительный код |
---|---|
... | ... |
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 |
... | ... |
Преобразование в дополнительный код
[править | править код]Преобразование числа из прямого кода в дополнительный осуществляется по следующему алгоритму.
- Если старший (знаковый) разряд числа, записанного в прямом коде, равен 0, то число положительное и никаких преобразований не делается;
- Если старший (знаковый) разряд числа, записанного в прямом коде, равен 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 с.