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

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

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

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

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

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

Таким чином, два найстарших біти рядка перенесення утворюють комбінацію «01», що позначає арифметичне переповнення. Справді, 1010₂ = 10₁₀, що знаходиться за межами 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-бітової змінної найбільше число це 127₁₀ = 7F₁₆ = 01111111₂, а найменше: −128₁₀ = 80_{16,доп. код} = 10000000_{2,доп. код}. Відповідно, не для кожного числа можна записати протилежне. Операція зміни знаку може вимагати додаткової перевірки.

Приклад програмного перетворення

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

Див. також

• Прямий код
• Обернений код
• Цілочисельний тип
• Алгоритм Бута