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

Доповняльний код (англ. 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 розрядах, дорівнює , що дорівнює 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». У оберненому коді таке число є.

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

Див. також
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.