Існує кілька способів представити числа зі знаком у двійковій системі, кожен з яких має різні компроміси. Двоєдоповнення є звичайним кодуванням для цілих чисел зі знаком із фіксованою шириною на сучасних ЦП. Величина знака відокремлює знак від величини, цей підхід також використовується у форматах із плаваючою комою. Двійковий зсув, або надлишок K, додає фіксоване зміщення; Двійкові формати IEEE-754 використовують його для нормальних чисел. Ми порівняємо три кодування та побачимо, що кожне з них полегшить.

Наївна перша спроба: знак-величина

Найбільш інтуїтивно зрозумілий спосіб розширити двійкову систему до чисел зі знаком — зарезервувати крайній лівий біт як позначку знака — 0 для позитивного, 1 для негативного — і використовувати решту бітів для кодування величини як числа без знаку. Ця схема називається знак-величина.

Для 4-бітного прикладу +5 і -5 виглядають так:

$$\begin{aligned} +5_{10} &= 0101_2 \\ -5_{10} &= 1101_2 \end{aligned}$$

Величина 101 однакова; змінюється тільки знаковий біт. Це легко читати, але вимагає додаткової обробки цілочисельної арифметики.

Два нулі

Оскільки знаковий біт не залежить від величини, існує два представлення нуля:

$$\begin{aligned} +0_{10} &= 0000_2 \\ -0_{10} &= 1000_2 \end{aligned}$$

Нуль має бути одним. Наявність двох бітових шаблонів для нього змушує ЦП перевіряти рівність у спеціальному випадку, де 0000 == 1000 все одно має оцінюватися як істинне. Він також втрачає один із 16 можливих шаблонів у 4-бітах — у схемі знак-величина ми маємо лише 15 окремих значень у діапазоні [-7; 7], а не повних 16.

Арифметика не просто працює

З беззнаковим двійковим кодом a + b є простим — ви додаєте біт за бітом, поширюєте перенесення, готово. Знак-величина порушує це. Розглянемо 3 + (-3) у 4-бітній знаковій величині:

$$\begin{aligned} & \phantom{1}0011_2 \quad (+3) \\ +\; & \phantom{1}1011_2 \quad (-3) \\ \hline & \phantom{1}1110_2 \quad (?) \end{aligned}$$

Читання 1110 як величини знака дає -6 — надзвичайно неправильно. Звичайне двійкове додавання не знає, що верхній біт має бути знаком; він просто додає його разом із усім іншим. Для того, щоб арифметика знак-величина працювала, ЦП має перевіряти біти знаків обох операндів, вирішити, додавати чи віднімати величини, можливо, порівнювати величини, щоб визначити знак результату, і обробляйте регістр двох нулів окремо. Усе це перетворюється на додаткову логіку обробки знаків.

Саме ці проблеми спонукали до переходу до схеми, де знак є не окремим прапором, а арифметичним наслідком самого кодування — доповненням до двох.

Швидкий приклад доповнення до двох

Доповнення до двох є стандартним кодуванням для цілих чисел зі знаком на сучасних процесорах, і воно простіше, ніж здається.

У доповненні до двох крайній лівий біт (старший біт) відіграє подвійну роль: він бере участь у обчисленні, як і будь-який інший біт, і — коли значення інтерпретується як ціле число зі знаком — він також повідомляє вам знак (0 для невід’ємного, 1 для від’ємного). Це не окремий прапор, який знімається; знак випадає з арифметики, оскільки позиційна вага верхнього біта від’ємна.

Давайте візьмемо двійкове число 1011 і припустимо, що це ціле число зі знаком у доповненні до двох. Щоб його декодувати, ми використовуємо подібну позиційну нотацію, як і для беззнакового двійкового коду, де кожному біту надається ступінь двійки як його вага, але потужність верхнього біта заперечується. Для 4 бітів це виглядає так:

$$b_3 \cdot (-2^3) + b_2 \cdot 2^2 + b_1 \cdot 2^1 + b_0 \cdot 2^0$$

Зверніть увагу на те, що змінилося порівняно зі звичайним двійковим кодом без знаку: три молодші біти $b_2, b_1, b_0$ зберігають свої звичайні додатні ваги ($+4$, $+2$, $+1$), але верхній біт $b_3$ множиться на $-2^3 = -8$ замість $+2^3 = +8$. Цей єдиний поворот знака на верхній позиції - це вся схема. Узагальнюючи, для n-розрядного числа з двома доповненнями верхній біт має вагу $-2^{n-1}$ замість звичайного $+2^{n-1}$, а всі інші біти зберігають свої нормальні позитивні ваги.

Підключення 1011 до формули дає $-8 + 0 + 2 + 1 = -5$, а не 11 (те, що ви отримаєте, читаючи 1011 як звичайний двійковий беззнаковий код: $8 + 0 + 2 + 1$), а не -3 (яку величину знака дасть: верхній біт 1 означає від’ємне, нижні біти 011 величину кодування 3).

Як закодувати від’ємне число

У попередньому розділі ми розшифрували бітовий шаблон, який уже був у пам’яті. Але як нам піти іншим шляхом — почати з десяткового числа, наприклад -5, і створити 4-бітний шаблон, який його зберігає? Позиційна формула говорить вам, що означає шаблон, але вона прямо не говорить вам, як створити його для даного від’ємного значення.

На щастя, є простий рецепт, який щоразу створює правильний шаблон: беріть додатну версію числа, інвертуйте всі біти (0 → 1, 1 → 0) і додайте 1. Результатом є двокомплементне кодування від’ємного значення. (Ми побачимо пізніше, у розділі модульної арифметики, чому цей рецепт працює — поки що розглядайте його як механічну процедуру.)

Давайте використаємо його, щоб знайти представлення -5 у 4 бітах:

1. Почніть з двійкового коду для +5:

$$+5_{10} = 0101_2$$

2. Інвертувати всі біти:

$$0101_2 \rightarrow 1010_2$$

3. Додайте 1:

$$1010_2 + 0001_2 = 1011_2$$

Отже, -5 зберігається як 1011 у 4-бітовому доповненні до двох. Подвійна перевірка за допомогою формули зважених бітів: $-8 + 0 + 2 + 1 = -5$.

Чому використовується ця схема

Доповнення двох дозволяє ЦП використовувати ту саму схему додавання (фізичний апаратний блок, що складається з логічних вентилів, який виконує порозрядне додавання з перенесенням) як для знакової, так і для беззнакової арифметики.

Виконаємо додавання 5 + (-5):

$$\begin{aligned} & \phantom{1}0101_2 \quad (+5) \\ +\; & \phantom{1}1011_2 \quad (-5) \\ \hline & 10000_2 \end{aligned}$$

Перенесення верхнього біта відкидається, залишаючи 0000 — рівно нулю. Апаратному забезпеченню не потрібно перевіряти, чи підписані операнди, і йому не потрібен окремий шлях віднімання. Звичайне двійкове додавання просто працює.

Дві інші властивості випадають з цього кодування. По-перше, діапазон для n бітів $[-2^{n-1};\ 2^{n-1}-1]$ — для 4 бітів це [-8; 7], для 8 бітів [-128; 127]. Зауважте, що він асиметричний: на одне від’ємне значення більше, ніж додатне, тому що слот, який представлятиме -0 за схемою знак-величина, перепрофільовано для найбільш від’ємного числа. По-друге, існує точно один нульовий шаблон 0000, а не два 0000 і 1000.

Об’єднуючий принцип: модульна арифметика

Тепер давайте подивимося, чому доповнення до двох працює так, як воно працює. Єдина ідея, яка пояснює майже все про формат, така: n-бітна арифметика — це модульна арифметика на колі позицій $2^n$. Майже кожна інша властивість формату — рецепт flip-and-add-1, одноланцюговий аргумент, обертання при переповненні — безпосередньо випливає з цього єдиного фрейму.

Що означає “модульна арифметика”.

Обгортання n-розрядного додавання, віднімання та множення працюють за модулем $2^n$. Уявіть собі 4-розрядний годинник із 16 позиціями, кожна з яких має дві мітки: значення без знаку (зовнішнє) і значення зі знаком із двома доповненнями (внутрішнє). Це описує бітовий результат; правила мови можуть відрізнятися, оскільки переповнення зі знаком у C є невизначеною поведінкою:

Зверніть увагу, як підписані мітки розділяють коло на дві половини: права сторона містить невід’ємні значення 0–+7, ліва сторона містить від’ємні значення −1…−8 (сама позиція 8 — бітовий шаблон 1000 — містить найбільш від’ємне значення −8).

Про те, як працює цей годинник, варто згадати кілька речей:

• Кожна позиція містить один бітовий шаблон — беззнакова та підписана мітки є лише двома різними інтерпретаціями тих самих 4 бітів.
• Додавання 1 пересуне вас за годинниковою стрілкою на одну позицію.
• Поминувши 15, ви повертаєтеся до 0. На цьому годиннику 15 + 1 = 0, 15 + 2 = 1, 15 + 3 = 2 і так далі — будь-яке значення після 15 продовжує ходити по колу, потрапляючи на позицію 0, потім 1, потім 2.

Математики мають коротку нотацію для такої поведінки обертання: a ≡ b (mod n) читається як «a потрапляє в ту саму позицію годинника, що й b на годиннику з позицією n». Отже, наші підсумкові приклади з наведеного вище маркера можна записати як 16 ≡ 0 (mod 16), 17 ≡ 1 (mod 16), 18 ≡ 2 (mod 16) — кожен із них просто говорить про те, що число ліворуч припадає на ту саму позицію, що й число праворуч, коли ви ходите по колу з 16 позиціями. Тож 18 ≡ 2 (mod 16) просто каже, що 18 приземляється на тій же позиції, що й 2 на 16-позиційному годиннику — одне повне коло (16 кроків) плюс 2 додаткових.

a ≡ b (mod n) є відношенням, тоді як a mod n обчислює залишки. Для позитивного n a % n == b % n Python перевіряє конгруентність навіть для негативних операндів. У мовах, де % є залишком зі знаком, наприклад JavaScript, спочатку нормалізуйте обидва результати: ((a % n) + n) % n. Наприклад, -1 і 15 конгруентні за модулем 16, хоча JavaScript дає їм різні необроблені залишки.

Чому працює рецепт «переверни та додай-1».

Тепер ми маємо достатньо механізмів, щоб зрозуміти, чому попередній рецепт насправді створює правильне кодування для від’ємних чисел.

Центральним поняттям є адитивна інверсія. На модульному годиннику «негативний x» насправді не є знаком «мінус» — це будь-яка позиція годинника, яка при додаванні до x повертає вас на позицію 0. Ця позиція називається адитивною, оберненою до x, і її збереження в бітах є саме тим, що робить доповнення двох. І рецепт, який ми бачили раніше — візьміть додатну версію, інвертуйте всі біти та додайте 1 — робить саме це: це процедура на рівні бітів для обчислення адитивної інверсії.

Давайте знайдемо адитивну інверсію 5 на нашому 16-позиційному годиннику. Нам потрібна така позиція y, щоб 5 + y приземлився на 0. Починаючи з 5 і проходячи 11 крокує за годинниковою стрілкою, приземляється на 16, який переходить до 0. Отже, y = 11:

$$5 + 11 = 16 \equiv 0 \pmod{16}$$

Таким чином, адитивна інверсія 5 на 16-позиційному годиннику дорівнює 11. А 11 у двійковій системі є 1011 — саме той бітовий шаблон, який раніше створив рецепт flip-and-add-1 для −5.

Тепер ми можемо узагальнити те, що ми зробили з 5 і 11, на будь-яку кількість бітів. На позиційному годиннику $2^n$ адитивна інверсія будь-якого значення x дорівнює $2^n - x$, оскільки

$$x + (2^n - x) = 2^n \equiv 0 \pmod{2^n}$$

Отже, доповнення двох зберігає −x як бітовий шаблон для $2^n - x$, що читається як беззнаковий. Це те, що ми спостерігали на годиннику, де знакові негативні числа −1, −2, …, −8 сидять на тих самих позиціях годинника, що й беззнакові числа 15, 14, …, 8 — кожне з них є адитивною зворотною величиною свого позитивного відповідника.

Нарешті, flip-bits-then-add-1 — це лише швидкий спосіб обчислення $2^n - x$ на рівні бітів без фактичного віднімання:

• Перевертання кожного біта $x$ дає $2^n - 1 - x$ (цей проміжний продукт називається доповненням до одиниці). Для 4 бітів із $x = 5 =$ 0101: перевертання дає 1010, який читається як беззнаковий 10, і справді $16 - 1 - 5 = 10$.
• Додавання 1 дає $2^n - x$. Продовжуючи приклад: $10 + 1 = 11$, адитивна інверсія, яку ми обчислили вище.

Отже, рецепт — це не хитрий трюк, винайдений дизайнерами — це ярлик на бітовому рівні для обчислення модульної адитивної інверсії.

Весь формат в одному реченні

Доповнення до двох — це беззнакова модульна арифметика з іншим позначенням верхньої половини годинника. Ось і вся схема. Кожна властивість — рецепт, єдиний контур, обгортання, властивість одного нуля — є наслідком цієї однієї ідеї.

Це також пояснює, чому одна схема суматора обробляє як знакову, так і беззнакову арифметику. Апаратне забезпечення не знає чи не піклується про те, чи позначаєте ви позиції на годиннику як «підписані» чи «беззнакові». Це просто додає модуль $2^n$. Незалежно від того, чи ви інтерпретуєте шаблон 1101 як беззнаковий 13 або зізнаковий -3, ЦП розглядає обидва операнди як позиції годинника, йде вперед на кроки, що відповідають другому операнду, і приземляється на певній позиції. Дві інтерпретації випливають з того, як ви читаєте результат, а не з того, як ЦП його обчислює.

Двійковий зсув: схема IEEE-754

Двоє доповнення є чудовим у тому, для чого воно розроблене: робить арифметику цілих чисел зі знаком тією самою схемою, що й арифметика без знаку. Але коли ви відходите від фрази «Я хочу додавати та віднімати цілі числа зі знаком» і ставите різні запитання про представлення зі знаком, це починає відчувати себе ніяково. Такі питання, як:

• Як порівняти два значення зі знаком порозрядно, так само, як ЦП порівнює значення без знаку?
• Куди природним чином розташовуються спеціальні бітові шаблони (найменший, найбільший, нульовий) у просторі бітових шаблонів?
• Чи чітко кодування відокремлює «маленьке» від «великого» без гімнастики зі знаком-прапорцем?

У беззнаковому порядку бітових шаблонів 0111...1111 (найбільше позитивне значення) і 1000...0000 (найбільш негативне значення) розташовані поруч посередині. Перетин цієї межі призводить до стрибка значення зі знаком назад. Зміщене кодування дозволяє уникнути цього стрибка, що корисно під час порівняння експонент із плаваючою комою.

Таким чином, комп’ютерна арифметика використовує інше представлення зі знаком, коли ці властивості мають значення: двійкове зміщення (також називається зміщене двійкове або excess-K). Це схема, яку IEEE-754 використовує для експоненти кожного числа з плаваючою комою, і ми побачимо, чому пізніше. А поки що давайте розглянемо, як це насправді працює.

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

Спочатку ми знаходимо зміщення за формулою, згаданою в стандарті IEEE-754:

$$K = 2^{n-1} - 1$$

де n – кількість бітів. Отже, зсув для 4 бітів становить 7. Потім ми додаємо зсув до вихідного числа: 3 + 7 = 10.

Отримане число 10 — це те, як число 3 зберігається у двійковій схемі зміщення. Оскільки ми використовували десяткову систему, щоб отримати результуюче число 10, нам потрібно перетворити його в двійкову:

$$\begin{aligned} 10 &= 2 \cdot 5 + 0 \\ 5 &= 2 \cdot 2 + 1 \\ 2 &= 2 \cdot 1 + 0 \\ 1 &= 2 \cdot 0 + 1 \\ \\ 10_{10} &= 1010_2 \end{aligned}$$

Якщо ви не знаєте алгоритму перетворення або хочете знати, чому він працює, перегляньте мою статтю про алгоритми десятково-двійкового перетворення.

Визначення зсуву

Припустимо, у нас є лише 4 біти для зберігання чисел. Використання формули для перестановок із повторенням дає нам $2^4 = 16$ різних бітових шаблонів. Питання в тому, що представляють ці 16 цифр. Припустімо, ми зацікавлені в збереженні лише невід’ємних цілих чисел. Тоді діапазон:

$$[0; 15]_{10} \qquad [0000; 1111]_2$$

Але якщо ми включаємо від’ємні цілі числа, то діапазон може змінюватися:

$$\begin{aligned} [-1; 14]_{10} &\qquad [0000; 1111]_2 \\ [-7; 8]_{10} &\qquad [0000; 1111]_2 \\ [-8; 7]_{10} &\qquad [0000; 1111]_2 \end{aligned}$$

Тут цікаво те, що хоча ми змінюємо діапазон у десятковій системі, у двійковій системі він залишається незмінним, тільки тепер найменше число 0000 представляє від’ємне число. Це ніби це найменше число зсувається від нуля на 1 у першому випадку, 7 у другому та 8 у третьому.

Іншими словами, зсув K — це просто вибір де розділити фіксований діапазон шаблонів бітів між негативними та невід’ємними значеннями — він визначає, скільки слотів буде з кожного боку від нуля. Немає єдиного математичного стандарту для того, як це вибрати, лише умовність. Поширені два варіанти:

$$\begin{aligned} K &= 2^{n-1} \quad &\text{(equal split, range } [-2^{n-1};\ 2^{n-1}-1]) \\ K &= 2^{n-1} - 1 \quad &\text{(IEEE-754, range } [-(2^{n-1}-1);\ 2^{n-1}]) \end{aligned}$$

Для 4 бітів K = 8 дає рівноділений діапазон [-8; 7], тоді як K = 7 (вибір IEEE-754) дає діапазон [-7; 8] з одним додатковим позитивним значенням.

Припустімо, нам потрібно зберегти число 3 в 4 бітах. Ми використаємо формулу зміщення IEEE-754 $K = 2^{n-1} - 1$, яка для $n = 4$ дає $K = 7$. Це зміщення розділяє 16 бітових шаблонів на діапазон [-7; 8], тому бітовий шаблон 0000 представляє -7, а 1111 представляє 8. Тепер, якщо 0000 є -7, яке число нам потрібно додати, щоб отримати 3? Це 10. У цьому прикладі використовуються всі шаблони; IEEE-754 резервує поля експоненти з усіма нулями та всіма одиницями, як описано нижче.

Давайте подивимося, що це нам дає:

$$\begin{aligned} 0000_2 + 1010_2 &= 1010_2 \\ -7_{10} + 10_{10} &= 3_{10} \end{aligned}$$

Це показує, що число 3 зберігається як 1010 у двійковому форматі зі зміщенням 7. Крім того, має бути легко визначити, звідки походить операція додавання зсуву для отримання представлення числа у двійковому вигляді:

$$-7 + 10 = 3 \rightarrow 3 + 7 = 10$$

Нарешті, як наслідок, якщо ми додаємо зміщення, щоб отримати представлення числа у двійковій формі, ми повинні відняти його, щоб перетворити число назад до оригіналу.

Переваги над доповненням до двох

Найбільша перевага офсетного двійкового коду над доповненням до двох полягає в тому, що він дозволяє порівнювати числа, використовуючи лексикографічний порядок, без необхідності додаткових операцій. Наприклад, давайте порівняємо два числа 3 і -3, представлені 4 бітами. У двійковому коді зі зміщенням вони мають таке представлення:

$$\begin{aligned} 3_{10} &= 1010_2 \\ -3_{10} &= 0100_2 \end{aligned}$$

Порівнюючи порозрядно, комп’ютеру з першого біта відразу стає зрозуміло, що перше число більше. Лексикографічний порядок не можна застосувати до чисел, які зберігаються як доповнення до двох:

$$\begin{aligned} 3_{10} &= 0011_2 \\ -3_{10} &= 1101_2 \end{aligned}$$

Для їх порівняння комп’ютер повинен виконати додаткові операції.

Монотонне впорядкування є головною перевагою, і з цього випливає кілька важливих наслідків — і разом вони пояснюють, чому IEEE-754 спеціально вибрав двійковий зсув для експоненти з плаваючою комою.

Для додатних кінцевих двійкових чисел з плаваючою точкою інтерпретація кодування як цілого числа без знаку зберігає числовий порядок. Від’ємні значення та спеціальні значення потребують додаткової обробки; зміщені експоненти не усувають всю логіку порівняння з плаваючою точкою.

Схема також акуратно розміщує зарезервовані шаблони бітів на межах. Поля експоненти з усіма нулями та всіма одиницями знаходяться на двох крайніх значеннях діапазону, і IEEE-754 використовує їх як слоти для спеціальних значень — ±0 і субнормальних унизу, ±∞ і NaN у верхній частині. Зсув (наприклад, 1023 для fp64) вибирається таким чином, що придатні експоненти потрапляють між цими зарезервованими кінцевими точками, а субнормальні/поступове зниження працюють плавно, оскільки вони живуть поруч із точним нулем на нижньому кінці.

Отже, вибір не довільний — двійкове зміщення — це представлення, завдяки якому всі ці властивості стають на свої місця одночасно.

Коли діапазон асиметричний

Якщо кожен із бітових шаблонів $2^n$ представляє окреме послідовне ціле число та включено нуль, діапазон не може бути симетричним щодо нуля: симетричний діапазон потребує непарної кількості значень. Цей аргумент передбачає відсутність повторюваних кодувань або зарезервованих шаблонів.

Доповнення до двох має одне додаткове від’ємне значення. Зміщений двійковий файл може вибирати багато діапазонів через своє упередження; лише два варіанти, наведені вище, майже по центру, відрізняються одним значенням. Знак-величина має симетричний діапазон і два нулі. Його арифметика потребує іншої логіки, але вона не є математично недійсною.

Ви можете побачити це безпосередньо в константах IEEE-754: для fp64 використовуваний діапазон експоненти (після резервування) становить від -1022 до +1023, все ще відхилений на одиницю. Ось чому найбільший скінченний дубль становить близько $1.8 \times 10^{308}$, тоді як найменший нормальний позитивний дубль становить приблизно $2.2 \times 10^{-308}$ — величини близькі, але не рівні.

Щоб дізнатися, як чотири основні операції (додавання, віднімання, множення, ділення) фактично працюють над двома доповненими цілими числами — і що відбувається на бітовому рівні, коли вони переповнюються або іншим чином порушуються — див. Як працює двійкова арифметика: цілі числа в додатковому коді та числа з рухомою комою IEEE-754.