Дополнительный код (представление числа)

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

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

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

Содержание

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

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

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

Примеры:

Десятичное
представление
Код двоичного представления (8 бит)
прямой дополнительный
127                 01111111                 01111111                
1                 00000001                 00000001                
0                 00000000                 00000000                
-0                 10000000                 --------                
-1                 10000001                 11111111                
-2                 10000010                 11111110                
-3                 10000011                 11111101                
-4                 10000100                 11111100                
-5                 10000101                 11111011                
-6                 10000110                 11111010                
-7                 10000111                 11111001                
-8                 10001000                 11111000                
-9                 10001001                 11110111                
-10                 10001010                 11110110                
-11                 10001011                 11110101                
-127                 11111111                 10000001                
-128                 --------                 10000000                

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

10-ричная система счисления
("обычная" запись)
10-ричная система счисления,
дополнительный код
... ...
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
... ...

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

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

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

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

101 

Инвертируем все разряды числа, получая таким образом обратный код:

010

Добавим к результату 1

011

Допишем слева знаковый единичный разряд

1011

Для обратного преобразования используется тот же алгоритм. А именно:

1011

Инвертируем все разряды числа, получая таким образом обратный код:

0100

Добавим к результату 1 и проверим, сложив с дополнительным кодом

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

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

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

Реализация алгоритма преобразования в обратный код

Pascal

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

C/C++

if (a < 0)
  a = (~a)|128;

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

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

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

Недостатки

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

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

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

C# .NET / C style

byte b1 = 254; //11111110 (бинарное)
byte b2 = 121; //01111001 (бинарное)
int c = (int)Math.Pow(2,(sizeof(byte)*8)-1);  //2 возводится в степень 7. Результат: 10000000 (бинарное)
int b1Conversion=(c ^ b1) - c;  //Результат: -2. А фактически, двоичный дополнительный код.
int b2Conversion=(c ^ b2) - c;  //Результат остаётся 121, потому что знаковый разряд - нуль.

См. также

Ссылки

  1. http://matlab.exponenta.ru/fixedpoint/book1/1.php К.Г.Жуков "Справочное руководство пользователя Fixed-Point Blockset" 1.2. Понятие прямого, обратного и дополнительного кодов, Определение 3.
  2. http://en.wikipedia.org/wiki/Two's_complement
Личные инструменты

Served in 0.317 secs.