Дополнительный код: представление отрицательных чисел

Почти все современные процессоры хранят целые числа в дополнительном коде (two's complement). Это не произвольный выбор: именно он позволяет складывать положительные и отрицательные числа одной и той же схемой, без специального флага знака и без дополнительных схем вычитания. Ниже разберём, как устроено это представление, почему диапазон чисел несимметричен, как перевести любое отрицательное число и где чаще всего ошибаются студенты. Для наглядности используй калькулятор ниже: он показывает двоичный и шестнадцатеричный код, вклад каждого разряда и положение числа на «кольце» кодов.

Почему не просто добавить бит знака

Наивная идея: взять двоичное представление числа и добавить к нему отдельный бит знака (0 - плюс, 1 - минус). Называется такой формат «прямой код». Проблема: у нуля появляются два представления - $00000000_2$ и $10000000_2$ - и сложение с отрицательными числами требует отдельной схемы с вычитателем. Дополнительный код решает обе проблемы разом.

Рассчитать для своей задачи

Ключевая идея: старший разряд (MSB) получает отрицательный вес $-2^{N-1}$, остальные разряды сохраняют обычные положительные веса $2^{N-2}, 2^{N-3}, \ldots, 2^0$. Значение числа по $N$-битному слову $b_{N-1}b_{N-2}\ldots b_0$ определяется формулой:

$x = -b_{N-1}\cdot 2^{N-1} + \sum_{k=0}^{N-2} b_k \cdot 2^k.$

Именно поэтому слово $10000000_2$ в 8 битах означает не $-0$, а $-128$: единица в знаковом разряде вносит вес $-2^7 = -128$, а все остальные биты нулевые.

Диапазон и несимметричность

В $N$-битном дополнительном коде можно представить числа от $-2^{N-1}$ до $+2^{N-1}-1$:

$\text{мин} = -2^{N-1}, \qquad \text{макс} = 2^{N-1}-1.$

Диапазон несимметричен: отрицательных чисел на одно больше, чем положительных. Так происходит потому, что ноль «занимает» место в положительной половине. Для 8 бит: от $-128$ до $127$, для 16 бит: от $-32768$ до $32767$, для 32 бит: от $-2\,147\,483\,648$ до $+2\,147\,483\,647$.

Эта несимметрия имеет практические последствия. В языке C стандарт гарантирует, что тип int вмещает как минимум $[-2^{15}, 2^{15}-1]$, а на большинстве 32-битных платформ - $[-2^{31}, 2^{31}-1]$. Функции наподобие abs() и Math.abs() возвращают неожиданный результат для минимального значения, потому что его положительный аналог не помещается в тот же тип.

Рассчитать для своей задачи

Показательный пример: $-1$ в 8 битах записывается как $11111111_2$ (все единицы), а $-128$ - как $10000000_2$ (только знаковый бит). Для $-128$ не существует положительного двойника той же разрядности: $+128$ уже не помещается в 8-битный диапазон и требует 9 битов.

Как переводить число в дополнительный код

Три эквивалентных способа.

Способ 1: через вычитание из $2^N$. Для отрицательного числа $x$ его $N$-битный дополнительный код - это беззнаковое значение $2^N - |x|$.

Пример: $-45$ в 8 битах $\Rightarrow$ $256 - 45 = 211 = 11010011_2$.

Способ 2: инверсия плюс единица. Берём абсолютное значение $|x|$, записываем его в двоичном виде, инвертируем все биты (заменяем 0 на 1 и наоборот), добавляем 1.

$|{-45}| = 45 = 00101101_2 \xrightarrow{\text{инверсия}} 11010010_2 \xrightarrow{+1} 11010011_2$.

Способ 3: по весам разрядов. Строим единственную комбинацию битов $b_k$, при которой $-b_7\cdot128 + \sum_{k=0}^{6} b_k\cdot2^k = -45$. Знаковый бит обязательно 1 (число отрицательное), тогда $-128 + S = -45 \Rightarrow S = 83 = 64+16+2+1$, то есть $b_6b_5b_4b_3b_2b_1b_0 = 1010011_2$. Итог: $11010011_2$.

Все три способа дают одинаковый результат.

Обратное преобразование: из кода в число

Чтобы прочитать знаковое значение из дополнительного кода, можно воспользоваться той же формулой весов: если старший бит равен 1, число отрицательное; его величина считается как $-(2^N - u)$, где $u$ - беззнаковая интерпретация того же слова.

Пример: $11010011_2 = 211_{10}$ (без знака). Знаковый бит единица, значит $x = 211 - 256 = -45$.

Этот алгоритм используют и процессоры, и компиляторы при разыменовании. Когда ты объявляешь переменную как знаковый тип - компилятор читает старший бит как отрицательный вес. Беззнаковый тип той же разрядности использует тот же битовый паттерн, но интерпретирует старший бит как обычный положительный вес $+2^{N-1}$. Именно поэтому приведение $-1$ (знаковый int8) к беззнаковому uint8 даёт $255$: те же биты $11111111_2$, другая интерпретация.

Сложение работает «само»

Главное преимущество дополнительного кода: сложение двух N-битных чисел с любыми знаками выполняется одной схемой обычного двоичного сумматора, а результирующий N-битный код даёт правильный ответ при отсутствии переполнения.

$(-45) + (+18) = 11010011_2 + 00010010_2 = 11100101_2 = -27.$

Перенос из старшего разряда отбрасывается. Вычитание $a - b$ реализуется как $a + (-b)$, то есть сложение с дополнительным кодом $b$. Чтобы получить $-b$, достаточно инвертировать биты и прибавить 1 - ровно та же операция, что и при переводе в дополнительный код.

Это свойство позволяет процессору использовать единственный сумматор для всей целочисленной арифметики. В прямом коде потребовалось бы отдельное устройство для вычитания, отдельное для инвертирования знака и логика выбора между операциями. Дополнительный код устраняет эту сложность на аппаратном уровне, что стало одной из главных причин его повсеместного принятия в 1960-х годах.

Переполнение

Переполнение происходит, когда истинный результат операции выходит за диапазон $N$-битного представления. Процессор обнаруживает его по флагу V (overflow): он устанавливается, когда знак сложения двух чисел с одинаковыми знаками не совпадает со знаком результата.

Пример: в 8 битах $100 + 50 = 150$, но $150 > 127$, поэтому код $10010110_2$ интерпретируется как $-106$ - неверный знаковый результат с установленным флагом V. Знаковый бит у обоих операндов равен 0 (оба положительны), а у результата равен 1 (отрицательный) - именно это несоответствие и сигнализирует переполнение.

Рассчитать для своей задачи

Правило детекции переполнения при сложении: если оба слагаемых положительны и сумма отрицательна (или оба отрицательны и сумма положительна) - произошло переполнение. При вычитании и при сложении разных знаков переполнение невозможно.

Частые ошибки

• Инвертировать биты, но забыть прибавить единицу. Результат после инверсии - обратный код (ones' complement), а не дополнительный. Без +1 значение на 1 больше нужного.
• Перепутать диапазон. В 8 битах минимум $-128$, максимум $+127$, а не $\pm127$. Попытка записать $+128$ в int8_t - UB в C/C++ и переполнение в аппаратной арифметике.
• Читать код без учёта разрядности. Код $1111_2$ в 4 битах означает $-1$, но $00001111_2$ в 8 битах - это $+15$. Разрядность контекста критична.
• Вычислять дополнение от нуля как $2^N$. Число 0 в дополнительном коде - ровно $N$ нулей; специального кода для $-0$ нет.
• Переполнение при смене знака $-2^{N-1}$. Это единственное число, для которого операция «взять противоположное» не работает в той же разрядности: $-(-128) = +128$ не помещается в 8-битный int.

FAQ

Чем дополнительный код отличается от прямого и обратного? Прямой код хранит знак отдельным битом, имеет два нуля и требует специального вычитателя. Обратный код получается инверсией всех битов модуля; у него тоже два нуля ($00000000$ и $11111111$), и сложение требует циклического переноса. Дополнительный код = обратный + 1, один ноль, обычный двоичный сумматор. Именно поэтому все современные архитектуры (x86, ARM, RISC-V) используют дополнительный код для знаковых целых.

Как узнать знак числа по дополнительному коду, не разворачивая вычисления? Достаточно посмотреть на старший (левый) бит: 0 - число неотрицательное, 1 - отрицательное. Это прямое следствие того, что старший бит имеет отрицательный вес $-2^{N-1}$.

Почему отрицательных чисел на одно больше, чем положительных? Ноль требует своего представления. Все $2^N$ возможных кодов распределяются так: один под ноль, $2^{N-1}-1$ под положительные и $2^{N-1}$ под отрицательные. «Лишнее» отрицательное число - это $-2^{N-1}$, у которого нет симметричного двойника в той же разрядности.

Коротко

Дополнительный код - стандартный способ хранить знаковые целые в компьютере: старший разряд получает отрицательный вес $-2^{N-1}$, остальные - обычные положительные веса. Диапазон N-битного числа: от $-2^{N-1}$ до $2^{N-1}-1$. Отрицательное число получают тремя путями: формулой $2^N - |x|$, инверсией плюс единица или подбором по весам. Главное преимущество формата - сложение и вычитание реализуются единой схемой без дополнительной логики знака.