Переполнение и диапазоны типов

Почему у целочисленных типов есть жёсткие границы и что происходит, когда число «не помещается» в отведённые биты.

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

В двух предыдущих уроках мы складывали, вычитали и кодировали отрицательные числа в фиксированном числе битов. Но у фиксированной разрядности есть цена: чисел, которые можно записать в $n$ битах, ровно $2^n$ — ни одним больше. Что произойдёт, если прибавить к самому большому числу единицу? Оно «перепрыгнет» в самое маленькое. Это и есть переполнение — источник коварных ошибок в программах и любимая тема экзаменационных задач про типы данных.

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

Переполнение объясняет реальные баги: счётчик, который вдруг стал отрицательным; «зависший» прогресс-бар; знаменитые сбои в старых играх, где здоровье или счёт обнулялись. Понимание диапазонов помогает выбрать правильный тип (int8, int16, int32, int64) и предсказать поведение арифметики. На экзамене часто спрашивают: «сколько целых чисел можно закодировать в $k$ битах» и «каков диапазон знакового типа» — это прямое применение формул ниже.

Сколько чисел помещается в n битов

В $n$ битах ровно $2^n$ различных комбинаций. Как мы их трактуем — зависит от того, знаковый тип или беззнаковый.

Для беззнакового типа (unsigned) все комбинации — это неотрицательные числа от 0 до $2^n - 1$:

$$ [\,0;\ 2^{n} - 1\,] $$

Для знакового типа (signed, в дополнительном коде) половина комбинаций уходит под отрицательные числа, половина — под неотрицательные, поэтому диапазон несимметричен:

$$ [\,-2^{\,n-1};\ 2^{\,n-1} - 1\,] $$

Несимметричность ($-128$ есть, а $+128$ нет) — следствие того, что ноль занимает одну из «положительных» ячеек. Подставим конкретные разрядности в таблицу — её полезно знать наизусть:

Проверьте по формуле: для int16 знаковая верхняя граница $2^{15} - 1 = 32767$, нижняя $-2^{15} = -32768$. Сходится.

Что происходит при переполнении

Поскольку битов фиксированное число, арифметика идёт по модулю $2^n$: всё, что вылезает за старший разряд, отбрасывается. Возьмём беззнаковый int8 (диапазон 0..255) и прибавим 1 к 255. В битах $255 = 11111111$, прибавляем 1:

Девятый бит не помещается в 8 разрядов и теряется — остаётся 00000000 = 0. Число «завернулось» с 255 на 0: это и есть циклический перенос (wrap-around). Можно представить шкалу как замкнутое кольцо: за 255 снова идёт 0, а перед 0 стоит 255.

У знакового типа кольцо то же, но граница «склейки» в другом месте — между $+127$ и $-128$. Прибавим 1 к $127$ (int8 signed). $127 = 01111111$, плюс 1 даёт 10000000, а это в дополнительном коде $-128$. То есть 127 + 1 = -128! Самое большое положительное число внезапно становится самым маленьким отрицательным. Именно так счётчики «уходят в минус».

Как это работает

Процессор всегда считает по модулю разрядности — он физически не может хранить лишние биты. Формально для беззнакового типа результат любой операции — это

$$ r = (a + b) \bmod 2^{n} $$

Для знакового действует тот же модуль, но с «переносом начала координат»: значения от $2^{n-1}$ до $2^n - 1$ трактуются как отрицательные ($v - 2^n$). Поэтому формула перевода беззнакового кода $u$ в знаковое значение такова: если $u \lt 2^{n-1}$, то число равно $u$; иначе оно равно $u - 2^n$. Высокоуровневые языки (C, C++, Java, Rust, Go) ведут себя по этим правилам для фиксированных типов. А вот Python особенный: его целые числа неограниченной разрядности (bignum), поэтому в нём переполнения нет вовсе — число просто растёт. Чтобы смоделировать поведение int8, мы вручную берём остаток по модулю $2^n$ и корректируем знак.

def wrap(value, bits=8, signed=True):
    """эмуляция переполнения целого типа на bits разрядов"""
    mod = 1 << bits              # 2**bits
    u = value % mod              # арифметика по модулю 2^n
    if signed and u >= (1 << (bits - 1)):
        u -= mod                 # старшая половина -> отрицательные
    return u

print("unsigned int8: 255 + 1 =", wrap(255 + 1, 8, signed=False))
print("signed   int8: 127 + 1 =", wrap(127 + 1, 8, signed=True))
print("signed   int8: -128 - 1 =", wrap(-128 - 1, 8, signed=True))
print("signed  int16: 32767 + 1 =", wrap(32767 + 1, 16, signed=True))
print("диапазон int8 signed: [", wrap(0, 8) - 128, ";", (1 << 7) - 1, "]")

Вывод:

unsigned int8: 255 + 1 = 0
signed   int8: 127 + 1 = -128
signed   int8: -128 - 1 = 127
signed  int16: 32767 + 1 = -32768
диапазон int8 signed: [ -128 ; 127 ]

Видно симметрию кольца: за верхней границей сразу идёт нижняя. 127 + 1 даёт $-128$, а -128 - 1 возвращает 127 — мы «прошли по кругу» в обе стороны.

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

• Считают диапазон знакового типа симметричным. Нет: $[-2^{n-1};\ 2^{n-1}-1]$, отрицательных чисел на одно больше, потому что ноль «съедает» одну положительную ячейку.
• Путают границы беззнакового и знакового. Беззнаковый $int8$ — это 0..255, знаковый — −128..127, а не 0..255 со знаком.
• Думают, что переполнение «вылетает с ошибкой». В большинстве компилируемых языков оно тихо заворачивается по модулю — программа продолжает работать с неправильным числом, и баг тяжело заметить.
• Переносят поведение Python на другие языки. В Python целые «бесконечны» и не переполняются; в C/C++/Java/Go — переполняются. Не путайте две модели.

Итоги

• В $n$ битах помещается $2^n$ значений: беззнаковый диапазон $[0;\ 2^n - 1]$, знаковый — $[-2^{n-1};\ 2^{n-1} - 1]$.
• Арифметика фиксированной разрядности идёт по модулю $2^n$: лишние старшие биты теряются.
• При переполнении значение заворачивается по кругу: у беззнакового после $2^n - 1$ идёт 0, у знакового после $2^{n-1}-1$ идёт $-2^{n-1}$.
• Типы int8/16/32/64 отличаются только числом битов; Python с его bignum переполнение не моделирует — его приходится эмулировать вручную через остаток по модулю.