Доповняльний код

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Доповня́льний код (англ. two’s complement, «доповнення до 2») — найпоширеніший спосіб представлення від'ємних чисел у комп'ютерах. Дозволяє замість команди віднімання використовувати команду додавання, для знакових і беззнакових чисел, що зменшує вимоги до архітектури комп'ютера. Доповняльний код від'ємного числа можна отримати так: інвертувати модуль числа у двійковому вигляді («перше доповнення») і додати одиницю («друге доповнення») або відняти число від нуля. Математично доповняльний код Xдоп = 2N+1 — X, де X — число, яке треба представити у доповняльному коді, N — к-сть розрядів числа.

Найстарший біт
0 1 1 1 1 1 1 1 = 127
0 1 1 1 1 1 1 0 = 126
0 0 0 0 0 0 1 0 = 2
0 0 0 0 0 0 0 1 = 1
0 0 0 0 0 0 0 0 = 0
1 1 1 1 1 1 1 1 = −1
1 1 1 1 1 1 1 0 = −2
1 0 0 0 0 0 0 1 = −127
1 0 0 0 0 0 0 0 = −128

Восьмирозрядні доповняльні коди

Подання від'ємного числа у доповнювальному коді[ред.ред. код]

При записі числа в доповнювальному коді старший розряд є знаковим. Якщо його значення дорівнює 0, то в решті розрядах записано позитивне двійкове число, що збігається з прямим кодом.

Двійкове 8-розрядне число зі знаком в доповняльному коді може представляти будь-яке ціле в діапазоні від -128 до +127. Якщо старший розряд дорівнює нулю, то найбільше ціле число, що може бути записано в останніх 7 розрядах, дорівнює  2 ^ 7-1 , що дорівнює 127.

Приклади:

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

Доповняльний код для десяткових чисел[ред.ред. код]

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

При застосуванні тієї ж ідеї до звичної 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

І перевіримо, склавши з доповнювальним кодом

 0101 + 1011 = 10000, п'ятий розряд викидається.

Р-адичні числа[ред.ред. код]

В системі p-адичних чисел зміна знаку числа здійснюється перетворенням числа в його доповняльний код. Наприклад, якщо використовується 5-річна система числення, то число, протилежне 1000 ... (1), так само є 4444 .... (-1).

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

Pascal[ред.ред. код]

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

C/C++[ред.ред. код]

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

Переваги та недоліки[ред.ред. код]

Переваги[ред.ред. код]

  • Комірка пам'яті може містити як n-бітні додатні числа, так і (n−1)-бітні числа зі знаком, причому операції додавання, віднімання і зсуву вліво однакові для обох форматів.
  • Відсутність числа «-0». У коді доповнення до 1 таке число є.

Недоліки[ред.ред. код]

  • Стосовно складних форматів (таких, як плаваюча кома або двійково-десятковий код) переваги втрачаються.
  • Модуль найбільшого числа не дорівнює модулю найменшого. Наприклад, для знакової цілої 8-байтової змінної найбільше число це 12710 = 7F16 = 011111112, а найменше: −12810 = 8016,доп. код = 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, тому що знаковий розряд - нуль.

Див. також[ред.ред. код]