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

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

Доповня́льний код (англ. 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).

Арифметичні операції[ред.ред. код]

Додавання[ред.ред. код]

Додавання двох чисел у доповняльному коді не потребує додаткових дій якщо доданки мають протилежні знаки, у такому випадку знак суми визначається автоматично. Приклад додавання 15 та -5:

  11111 111   (перенесення)
   0000 1111  (15)
 + 1111 1011  (−5)
 ==================
   0000 1010  (10)

Цей процес залежить від обмеження вісьма бітами: перенесення до відсутнього дев'ятого найстаршого біту ігнорується, що повертає нам правильний результат 1010.

Найстарші два біти рядка перенесених цифр містять важливу інформацію: коли обчислення призвело до арифметичного переповнення, число занадто велике для представлення у двійковій системі (у цьому випадку більше ніж 8 біт). Переповнення існує тоді, коли ці два біти відрізняються один від одного. Як уже згадувалося, знак кодується в старшому біт результату.

Іншими словами, коли обидва старші біти рядка перенесення 1 або 0, обчислення дало правильний результат, але коли вони утворюють комбінацію "10" або "01", трапилося знакове переповнення. Зручно те, що операція XOR, виконана над цими двома бітами, показує чи була операція виконана коректно. Як приклад, розглянемо 4-бітове додавання 7 та 3:

  0111   (перенесення)
   0111  (7)
 + 0011  (3)
 =============
   1010  (−6)  некоректно!

Таким чином, два найстарших біти рядка перенесення утворюють комбінацію "01", що позначає арифметичне переповнення. Справді, 10102 = 1010, що знаходиться за границями 4-бітових чисел −8 та 7.

Загалом, будь-які N-бітові числа можуть бути додані без переповнення, якщо перед цим їх перевести до N + 1 бітового вигляду і після цього додати. Границі N + 1 бітових чисел більш ніж в двічі перевищують границі N-бітових чисел, тож у новій системі переповнення ніколи не виникне.

Реалізація алгоритму перетворення в доповнювальний код (для 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, тому що знаковий розряд - нуль.

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