Знаковые числа можно представить в двоичной системе несколькими способами, у каждого свои компромиссы. Дополнительный код обычно используется для знаковых целых фиксированной разрядности на современных процессорах. Прямой код отделяет знак от модуля; такой подход используется и в форматах с плавающей точкой. Смещённый код, или excess-K, добавляет постоянное смещение; двоичные форматы IEEE-754 используют его для порядков нормализованных чисел. Сравним эти три представления.

Наивная первая попытка: прямой код

Самый интуитивный способ расширить двоичную запись на знаковые числа — отвести крайний левый бит под флаг знака (0 для положительных, 1 для отрицательных), а остальными битами закодировать величину как беззнаковое число. Такая схема называется прямым кодом (sign-magnitude).

Для примера на 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$ позиций. Почти любое другое свойство формата — рецепт «инвертируй и прибавь 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»

Теперь у нас достаточно инструментов, чтобы понять, почему приведённый ранее рецепт действительно даёт правильное кодирование отрицательных чисел.

Центральное понятие — противоположное число (additive inverse). На модульном циферблате «минус 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, в точности тот битовый шаблон, который ранее выдал рецепт «инвертируй и прибавь 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: каждое из них — противоположное число к соответствующему положительному значению.

Наконец, «инвертировать биты, затем прибавить 1» — это просто быстрый побитовый способ вычислить $2^n - x$, не выполняя настоящего вычитания:

• Инвертирование каждого бита $x$ даёт $2^n - 1 - x$ (это промежуточное значение называется обратным кодом, one’s complement). Для 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 (наименьшее отрицательное) соседствуют в середине диапазона. При переходе через эту границу знаковое значение скачком уменьшается. Кодирование со смещением устраняет такой скачок, что удобно при сравнении порядков чисел с плавающей точкой.

Поэтому компьютерная арифметика использует другое знаковое представление, когда эти свойства важны: смещённый код (offset binary, он же biased binary или excess-K). Именно эту схему IEEE-754 применяет к порядку каждого числа с плавающей точкой, и почему именно — мы увидим позже. А пока посмотрим, как она работает.

Процедура кодирования в смещённом коде проста: вычисляем смещение (bias), прибавляем его к числу, которое хотим сохранить, и получившееся значение и есть то, что реально записывается (при необходимости переведённое в двоичный вид). Чтобы продемонстрировать шаги, посмотрим, как число 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{(равное деление, диапазон } [-2^{n-1};\ 2^{n-1}-1]) \\ K &= 2^{n-1} - 1 \quad &\text{(IEEE-754, диапазон } [-(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.