Користувач:Khristoiev Konstantin/Чернетка

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

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

Див. також

• Обернений код
• Прямий код
• Цілочисельний тип
• Код доповнення до 1