Прямой, обратный и дополнительный код

Разбираемся, как записать отрицательное число одними нулями и единицами и почему процессор умеет вычитать, умея только складывать.

Дополнительный код (two's complement) — способ представления отрицательных целых чисел, при котором число $-x$ в $n$ разрядах записывается как $2^n - x$, благодаря чему вычитание заменяется сложением.

В прошлом уроке мы столкнулись с проблемой: что делать, если из меньшего числа вычесть большее? Результат отрицателен, а в обычной двоичной записи знака «минус» нет — есть только нули и единицы. Компьютер решает это хитро: один из битов он назначает знаковым, а сами отрицательные числа кодирует так, чтобы сложение «само» давало правильный ответ. Эта тема — ядро понимания целочисленной арифметики и постоянный гость экзаменов и собеседований.

Зачем это нужно

Без знаковых кодов невозможно объяснить, почему в Python -1 в восьми битах выглядит как 11111111, почему int8 хранит числа от −128 до 127, и почему вычитание в процессоре — это та же схема сумматора. Дополнительный код используется во всех современных процессорах; понимая его, вы понимаете, как «думает» железо.

Знаковый бит и прямой код

Договоримся работать в $n$ разрядах (для примеров возьмём $n = 8$). Старший бит объявляем знаковым: 0 — число положительное, 1 — отрицательное. Оставшиеся $n - 1$ битов хранят величину. Это и есть прямой код (sign-magnitude). Например, $+5$ — это 00000101, а $-5$ в прямом коде — 10000101 (тот же модуль 5, но знаковый бит = 1).

Прямой код нагляден, но у него два изъяна. Во-первых, два представления нуля: 00000000 и 10000000 («плюс ноль» и «минус ноль»). Во-вторых, и это главное, складывать в нём напрямую нельзя: 00000101 (+5) плюс 10000101 (−5) даёт 10001010, что вовсе не ноль. Поэтому процессоры прямой код для арифметики не используют.

Обратный код: инверсия битов

Обратный код (one's complement) отрицательного числа получают так: берут прямой код модуля и инвертируют все биты (нули становятся единицами и наоборот). Для $-5$: модуль 5 — это 00000101, инвертируем — 11111010. Знаковый бит при этом сам становится 1, что логично для отрицательного числа.

Обратный код уже ближе к цели — при сложении он почти работает, — но у него остаётся неприятность: «циклический перенос» (если из старшего разряда вышел перенос, его надо прибавить к младшему) и по-прежнему два нуля (00000000 и 11111111). Поэтому он используется как промежуточный шаг к по-настоящему удобному дополнительному коду.

Дополнительный код: главный герой

Дополнительный код получается из обратного прибавлением единицы. Правило в три шага: (1) записать модуль в прямом коде; (2) инвертировать все биты — получили обратный код; (3) прибавить 1. Для $-5$ в 8 битах:

Итак, $-5$ в дополнительном коде — это 11111011. Формула, по которой это считается напрямую, выражается через степень двойки:

$$ \text{доп.код}(-x) = 2^n - x, \qquad 0 \lt x \le 2^{n-1} $$

Проверим: $2^8 - 5 = 256 - 5 = 251$, а $251 = 11111011_2$. Та же запись, что мы получили шагами. Удобно держать в голове обе модели: «инвертировать и прибавить 1» — для ручного счёта, и «$2^n - x$» — для понимания, почему всё сходится.

Как это работает: вычитание = сложение

Главная магия дополнительного кода: чтобы вычесть, достаточно прибавить дополнительный код вычитаемого, а лишний перенос из старшего разряда просто отбросить. Посчитаем $7 - 5$ в 8 битах, ожидая 2:

При сложении 00000111 + 11111011 получается 9-битный результат 1 00000010. Девятый бит (перенос за пределы 8 разрядов) отбрасываем — остаётся 00000010 = 2. Именно поэтому в процессоре нет отдельной «схемы вычитания»: блок вычитания инвертирует второй операнд, подаёт перенос-вход равным 1 (это и есть «+1» дополнительного кода) и использует тот же сумматор. Почему перенос можно смело отбрасывать? Потому что $a + (2^n - b) = 2^n + (a - b)$, а слагаемое $2^n$ — это как раз тот самый бит за границей разрядной сетки, который не помещается и пропадает.

Проверим всё на Python. В Python целые числа неограниченной длины, поэтому «обрезку» до $n$ битов делаем вручную через маску (1 << n) - 1 (она равна $2^n - 1$, то есть $n$ единиц):

def twos(x, n=8):
    """дополнительный код числа x в n битах как строка"""
    mask = (1 << n) - 1          # n единиц: 0xFF для n=8
    return format(x & mask, "0" + str(n) + "b")

print("+5 ->", twos(5))
print("-5 ->", twos(-5))
print("-1 ->", twos(-1))
print("-128 ->", twos(-128))

# вычитание как сложение с доп.кодом
a, b = 7, 5
res = (a + (-b)) & 0xFF        # обрезали до 8 бит
print("7 - 5 =", res, "=", twos(7 - 5))

Вывод:

+5 -> 00000101
-5 -> 11111011
-1 -> 11111111
-128 -> 10000000
7 - 5 = 2 = 00000010

Обратите внимание на $-1$: это 11111111, то есть «все единицы», потому что $2^8 - 1 = 255$. А $-128$ — это 10000000: знаковый бит стоит, а величина нулевая, и это самое маленькое число для 8 бит. Запомните образ: в дополнительном коде у отрицательных чисел старший бит всегда 1.

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

• Забывают прибавить 1. Инвертировали биты и остановились — это обратный код, а не дополнительный. Дополнительный = инверсия + 1.
• Путают, какой бит знаковый. Знаковый — старший (самый левый), а не младший.
• Не дописывают число до полной разрядности. Кодировать надо ровно в $n$ битах: для 8 бит у $+5$ это 00000101, а не 101. Иначе инверсия даст неверный результат.
• Считают перенос ошибкой. Перенос за пределы $n$ разрядов при вычитании — это норма, его отбрасывают. Ошибкой переполнения он становится только в другом случае (см. следующий урок).

Итоги

• Старший бит — знаковый: 0 для положительных, 1 для отрицательных чисел.
• Прямой код = знак + модуль; обратный код = инверсия всех битов; дополнительный код = обратный + 1.
• Формула дополнительного кода: $-x$ записывается как $2^n - x$ в $n$ разрядах.
• Вычитание сводится к сложению с дополнительным кодом, а лишний перенос за границу разрядов отбрасывается — поэтому процессор обходится одним сумматором.