Доповняльний код (англ. 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 |
| ... | ... |
Перетворення у доповняльний код Редагувати
Перетворення числа з прямого коду в доповняльний здійснюється за таким алгоритмом.
- Якщо число, записане в прямому коді, додатне, то до нього дописується старший (знаковий) розряд, рівний 0, і на цьому перетворення закінчується;
- Якщо число, записане в прямому коді, від'ємне, то всі розряди числа (крім знакового) інвертуються, а до результату додається 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, тому що знаковий розряд - нуль. Див. також Редагувати
| Це незавершена стаття про програмування. Ви можете допомогти проєкту, виправивши або дописавши її. |
| Ця стаття не містить посилань на джерела. (листопад 2011) |