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

Урок объясняет дополнительный код — стандартный способ хранения целых со знаком, благодаря которому вычитание превращается в сложение.

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

Зачем не «знак и величина»

Самый наивный способ хранить знак — выделить один бит под «плюс/минус» (signed magnitude). Но тогда у нуля два представления (+0 и −0), а главное — сложение и вычитание требуют разной логики и проверки знаков. Дополнительный код решает обе проблемы: ноль один, а одна и та же схема сложения работает и для положительных, и для отрицательных. Это огромная экономия транзисторов в АЛУ.

Как получить дополнительный код

Чтобы получить -x: инвертировать все биты x и прибавить 1. Возьмём 8-битный пример для числа 5:

  5            = 0000 0101
  инверсия     = 1111 1010   (это "обратный код", ones' complement)
  + 1          = 1111 1011
  -5           = 1111 1011

Проверка: 5 + (-5) должно дать 0 в 8 битах:
  0000 0101
+ 1111 1011
-----------
 10000 0000  -> перенос за 8-й бит отбрасывается -> 0000 0000 = 0

Старший (левый) бит работает как знак: 0 — число неотрицательное, 1 — отрицательное. Диапазон 8-битного знакового числа: от −128 до +127 (а не до +128 — лишнее значение «съел» ноль и асимметрия).

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

Главная красота: a - b вычисляется как a + (-b), то есть a + (инверсия b) + 1. Не нужна отдельная схема вычитания. Проверим всё на чистом Python:

def twos_complement(x, bits=8):
    # вернуть n-битную строку дополнительного кода для x
    mask = (1 << bits) - 1
    return format(x & mask, f"0{bits}b")

def interpret(bitstr):
    # прочитать строку как знаковое число (дополнительный код)
    bits = len(bitstr)
    val = int(bitstr, 2)
    if bitstr[0] == "1":          # старший бит -> отрицательное
        val -= (1 << bits)
    return val

for x in (5, -5, 127, -128):
    code8 = twos_complement(x)
    print(f"{x:>5} -> {code8} -> обратно {interpret(code8)}")

print("Вычитание 9 - 4 через сложение:")
res = (9 + interpret(twos_complement(-4))) & 0xFF
print("  результат:", interpret(format(res, '08b')))

Вывод:

    5 -> 00000101 -> обратно 5
   -5 -> 11111011 -> обратно -5
  127 -> 01111111 -> обратно 127
 -128 -> 10000000 -> обратно -128
Вычитание 9 - 4 через сложение:
  результат: 5

Переполнение со знаком

Если сложить два больших положительных числа и сумма не влезет в разряды, знаковый бит «перевернётся» — получится отрицательный результат. Это переполнение (overflow): признак, что результат вышел за диапазон. Процессор поднимает специальный флаг переполнения.

def add8_signed(a, b):
    raw = (a + b) & 0xFF            # сложение в 8 битах
    val = raw - 256 if raw & 0x80 else raw
    # переполнение: знаки a и b одинаковы, а знак результата другой
    overflow = (a >= 0) == (b >= 0) and (val >= 0) != (a >= 0)
    return val, overflow

print(add8_signed(100, 50))   # 150 не влезает в +127
print(add8_signed(50, 20))

Вывод:

(-106, True)
(70, False)

Глубже: почему «инверсия плюс один» вообще работает

Формула «инвертировать биты и прибавить 1» поначалу выглядит как магический рецепт, но за ней стоит простая арифметика по модулю. В n-битном слове все вычисления идут «по кругу»: результат всегда берётся по модулю 2^n, потому что переносы за старший разряд отбрасываются. Инверсия всех битов числа x — это то же самое, что вычесть его из строки одних единиц, то есть получить (2^n − 1) − x. Прибавив единицу, имеем 2^n − x — а это ровно та величина, которая в сложении по модулю 2^n ведёт себя как −x, ведь x + (2^n − x) = 2^n ≡ 0. Вот почему сложение положительного и его дополнительного кода честно даёт ноль: они в сумме дают полный оборот колеса.

Эту «арифметику по кругу» удобно представлять как циферблат часов. Если сейчас 10 часов и нужно отмотать на 3 назад, можно либо вычесть 3, либо прибавить 9 (то есть 12 − 3) — результат одинаков, 7 часов. Дополнительный код делает ровно это: заменяет вычитание прибавлением «дополнения до полного круга». Поэтому одна и та же схема-сумматор обслуживает и плюс, и минус, не зная разницы.

Историческая справка: были и другие варианты

Дополнительный код не был единственным кандидатом и победил не сразу. Ранние машины пробовали «знак-величина» (отдельный бит знака) и «обратный код» (ones' complement, та самая инверсия без прибавления единицы). У обоих был один и тот же изъян, которого нет у дополнительного кода: два представления нуля, +0 и −0. Это казалось мелочью, но порождало коварные баги — сравнение x == 0 могло не сработать, если ноль «отрицательный». Машины на обратном коде (например, серия CDC) вынуждены были городить дополнительную логику «коррекции конца переноса». Дополнительный код устранил всё это разом, и к 1970-м стал безоговорочным стандартом для целых со знаком.

Любопытно, что отзвук «минус нуля» дожил до наших дней — но уже не в целых, а в числах с плавающей точкой (IEEE 754), где +0 и −0 существуют намеренно. Так что асимметрия диапазона дополнительного кода (на одно отрицательное больше) — это цена, заплаченная ровно за то, чтобы ноль был один и арифметика была проста.

Где переполнение кусает в реальности

Знаковое переполнение из этого урока — не учебная страшилка, а причина громких сбоев. Классический пример — деление видеоигр и финансовых систем, где счётчик в 32 бита внезапно «перепрыгивал» через +2 147 483 647 и становился огромным отрицательным. Печально известен запуск ракеты Ariane 5 (1996): при попытке уместить 64-битное дробное значение скорости в 16-битное целое произошло переполнение, бортовой компьютер выдал ошибку, и ракета самоликвидировалась через 37 секунд. Стоимость одной непроверенной арифметической границы — сотни миллионов долларов.

Отсюда важная привычка: в языках вроде C и Java целые имеют фиксированную разрядность и молча переполняются, поэтому критичные сложения и умножения нужно проверять на выход за диапазон заранее. Python в этом смысле щадящий — его целые растут произвольно, — но как только вы спускаетесь к реальному железу, флаг переполнения процессора и эти границы становятся вашей зоной ответственности.

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

Забывать прибавить 1 после инверсии. Просто инверсия даёт обратный код (ones' complement), а не дополнительный.
Путать переполнение и перенос. Перенос (carry) — выход за разрядность для беззнаковых; переполнение (overflow) — выход за диапазон для знаковых; это разные флаги.
Считать диапазон симметричным. Для n бит он от −2^(n−1) до +2^(n−1)−1: отрицательных значений на одно больше.

Итог

Дополнительный код: -x = инверсия битов x плюс 1; старший бит — знак.
Главное достоинство — вычитание сводится к сложению, ноль единственный.
Переполнение возникает, когда знаковая сумма выходит за диапазон; процессор поднимает флаг.