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

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

Зачем нужен дополнительный код

В прямом коде знак числа хранится в старшем бите: 0 - плюс, 1 - минус, а остальные разряды задают модуль. Просто, но неудобно: появляются два нуля (положительный и отрицательный), а вычитание требует отдельной логики сравнения знаков. Дополнительный код избавляется от обоих недостатков. В нём отрицательное число записывается так, что его сложение с положительным даёт правильный результат на том же сумматоре, который складывает беззнаковые числа. Ноль остаётся единственным, а диапазон используется полностью.

Главная идея: при фиксированной разрядности $N$ бит все коды живут по модулю $2^N$. Отрицательное число $x$ представляется тем же кодом, что и беззнаковое $2^N + x$. Например, в 8 битах число $-1$ кодируется как $2^8 - 1 = 255$, то есть все восемь единиц. Поэтому при переборе кодов от $0$ вверх мы доходим до максимума, а затем «переваливаем» в отрицательную область - отсюда и образ кольца.

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

Как старший бит получает отрицательный вес

Самое короткое определение дополнительного кода: это обычное позиционное двоичное представление, в котором вес старшего разряда взят со знаком минус. Для $N$ бит значение числа равно

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

где $b_k$ - значение $k$-го бита. Все младшие разряды дают привычные положительные веса $2^0, 2^1, \dots, 2^{N-2}$, и только старший разряд $b_{N-1}$ весит $-2^{N-1}$. Если он равен нулю, число положительно и совпадает с беззнаковым; если единице - к сумме добавляется большое отрицательное слагаемое, и число уходит в минус.

Возьмём канонический пример: 8-битный код $11010011$. Старший бит равен 1, значит вклад старшего разряда $-2^7 = -128$. Остальные единицы стоят в разрядах 6, 4, 1 и 0, давая $64 + 16 + 2 + 1 = 83$. Итог: $-128 + 83 = -45$. Тот же код, прочитанный как беззнаковое число, равен $211$, а в шестнадцатеричной записи это $0xD3$.

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

На схеме весов хорошо видно, почему дополнительный код «самосогласован»: чтение по весам и есть обратное преобразование. Не нужно отдельно смотреть на знак - достаточно просуммировать вклады разрядов, помня, что самый левый из них отрицательный.

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

Для отрицательного числа есть три эквивалентных пути, и в калькуляторе они дают один и тот же результат.

Первый - по формуле остатка. Код отрицательного числа $x$ равен беззнаковому представлению величины $2^N - |x|$. Для $x = -45$ и $N = 8$ это $256 - 45 = 211$, то есть $11010011_2$.

Второй - инверсия и плюс единица, самый удобный «ручной» способ. Записываем модуль числа в обычном двоичном виде, инвертируем все биты (получаем обратный код), затем прибавляем единицу:

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

Третий - через подбор по весам: подобрать единицы в разрядах так, чтобы их веса (с отрицательным старшим) дали нужное число. На практике им пользуются для проверки, а не для расчёта.

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

Чтобы перевести любое своё число в код и обратно, задай разрядность и подвинь ползунок в калькуляторе выше: он покажет двоичную и шестнадцатеричную запись, разложение по весам и положение числа на кольце кодов.

Диапазон представимых чисел и его несимметричность

При $N$ битах в дополнительном коде помещаются числа от $-2^{N-1}$ до $2^{N-1}-1$:

$-2^{N-1} \le x \le 2^{N-1}-1.$

Для 8 бит это от $-128$ до $127$, для 16 бит - от $-32768$ до $32767$. Диапазон несимметричен: отрицательных чисел на одно больше, чем положительных. Причина проста - один из $2^N$ кодов занят нулём, и он лежит в «положительной» половине, поэтому самому большому по модулю отрицательному числу $-2^{N-1}$ нет положительной пары. Отсюда известная ловушка: модуль числа $-128$ в 8 битах нельзя представить как $+128$, а попытка взять $-(-128)$ снова даёт $-128$.

Сложение, вычитание и переполнение

Главная награда за дополнительный код - арифметика. Чтобы вычесть, достаточно прибавить дополнительный код вычитаемого: $a - b = a + (\text{код}(-b))$. Перенос из старшего разряда просто отбрасывается, потому что вычисления идут по модулю $2^N$. Это и позволяет одному сумматору обслуживать оба знака.

Опасность одна - переполнение. Оно возникает, когда истинный результат выходит за диапазон $[-2^{N-1},\, 2^{N-1}-1]$. Признак переполнения: при сложении двух чисел одного знака получился результат противоположного знака. Например, в 8 битах $100 + 50 = 150$, но $150 > 127$, поэтому код «перескакивает» через границу и читается как $150 - 256 = -106$. Программный или аппаратный флаг переполнения как раз ловит ситуацию, когда перенос в старший разряд и перенос из него не совпадают.

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

• Инверсия без прибавления единицы. После инвертирования битов получается обратный код, а не дополнительный. Единицу прибавлять обязательно, иначе число будет меньше на единицу.
• Игнорирование разрядности. Дополнительный код не существует «вообще»: $-1$ - это $1111$ в 4 битах и $11111111$ в 8 битах. Без указания $N$ запись бессмысленна.
• Перевод старшего бита как обычного. Старший разряд весит $-2^{N-1}$, а не $+2^{N-1}$. Если прочитать его с плюсом, отрицательные числа превратятся в большие положительные.
• Симметричный диапазон. Граница не $\pm 2^{N-1}$, а от $-2^{N-1}$ до $2^{N-1}-1$. Число $-2^{N-1}$ есть, а его положительной пары нет.
• Незамеченное переполнение. Отброшенный перенос - это норма, а вот смена знака при сложении одинаковых знаков - сигнал, что результат недостоверен.

FAQ

Как перевести отрицательное число в дополнительный код вручную? Запишите модуль числа в двоичном виде в нужной разрядности, инвертируйте все биты и прибавьте единицу. Для $-45$ в 8 битах: $45 = 00101101$, инверсия $11010010$, плюс единица - $11010011$.

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

Чем дополнительный код лучше прямого и обратного? В нём единственный ноль и не нужна отдельная логика для вычитания: оно сводится к сложению. Прямой и обратный коды дают два нуля и требуют коррекции при переносе, поэтому в процессорах прижился именно дополнительный код.

Коротко

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