Целые числа в памяти

Начнём с простого случая – когда отрицательные числа не нужны вовсе.

Беззнаковое представление (unsigned) – способ записи целых чисел, при котором все биты отведены под само значение. Число читается как обычная двоичная запись: разряды с весами $2^0$, $2^1$, $2^2$, … и никаких исключений.

Диапазон беззнакового числа из n битов – от 0 до $2^n - 1$:

Обратите внимание на «− 1» в формуле: значений ровно $2^n$, но одно из них – ноль, поэтому максимум на единицу меньше. Восьмибитное максимальное значение – 255, а не 256.

Беззнаковое представление выбирают там, где отрицательное значение бессмысленно по смыслу задачи: размер файла в байтах, количество символов в строке, индекс элемента, яркость канала цвета (те самые 0–255 в RGB), адрес в памяти. Половина всех комбинаций при этом не тратится на минус – и максимум получается вдвое больше, чем у знакового числа той же ширины.

С фиксированной шириной связана особенность, которой нет у чисел на бумаге. Что будет, если к 255 в восьмибитной ячейке прибавить единицу?

На бумаге получится 256, то есть 100000000 – девять битов. Но девятый бит записывать некуда: ячейка вмещает восемь. Старший бит отбрасывается, и в ячейке остаётся 00000000 – ноль.

Переполнение – ситуация, когда результат операции не вмещается в отведённое число битов; лишние старшие биты теряются.

Ровно так же ведёт себя механический счётчик пробега: после 999 999 он показывает 000 000, потому что седьмого барабана в нём нет. Отсюда полезный образ: значения в ячейке фиксированной ширины замкнуты в кольцо, и за 255 сразу следует 0.

Классический пример из истории: в игре Pac-Man (1980) номер уровня хранился в одном байте. На 256-м уровне счётчик переполнился, и половина экрана превратилась в мусор из случайных символов – пройти этот уровень невозможно. Игроки прозвали его «уровнем-убийцей» (kill screen), и он до сих пор считается фактическим концом игры.

Самое очевидное решение для отрицательных чисел – поступить как на бумаге: отвести под знак отдельный символ. Битов у нас всего восемь, поэтому пожертвуем старшим: пусть он означает знак (0 – плюс, 1 – минус), а остальные семь хранят модуль числа.

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

Тогда:

Способ работает и человеку понятен. Но у него две беды, и обе серьёзные.

Беда первая: два разных нуля. Комбинация 00000000 – это «плюс ноль», а 10000000 – «минус ноль». Математически это одно и то же число, а в памяти – разные наборы битов. Значит, простое сравнение битов перестаёт отвечать на вопрос «равны ли числа»: приходится отдельно проверять случай нуля. И одна комбинация из 256 расходуется впустую.

Беда вторая, главная: арифметика ломается. Попробуем сложить 5 и −5 «в лоб», как обычные двоичные числа:

  00000101   (+5)
+ 10000101   (−5)
= 10001010

Получилось 10001010 – «минус 10». А должно получиться 0. То есть обычное двоичное сложение с прямым кодом не работает: сначала нужно сравнить знаки, потом сравнить модули, потом решить, складывать или вычитать, и какой знак поставить результату. Это уже не одна операция, а целый алгоритм с ветвлениями – и всё это пришлось бы реализовать схемами внутри процессора.

Сформулируем требование к представлению отрицательных чисел так, как его сформулировали бы инженеры:

хочется, чтобы вычитание было обычным сложением. Чтобы одна и та же схема сложения складывала и «5 + 3», и «5 + (−3)», не разбираясь в знаках.

Из блока 3 мы знаем, что схема сложения (сумматор из полусумматоров, урок 3.5) – вещь недешёвая, но зато однократная: собрал один раз и складывай что угодно. Если удастся свести вычитание к сложению, отдельная схема вычитания процессору не понадобится вовсе.

И подсказка, как этого добиться, уже была – в кольце из предыдущего раздела. Посмотрим, что лежит в ячейке, если из нуля вычесть единицу. Счётчик крутится назад: 0 → 255. То есть в восьмибитной ячейке 255 ведёт себя как −1: прибавьте к любому числу 255, отбросьте девятый бит – и получите то же самое, что при вычитании единицы. Проверим на 7:

  00000111   (7)
+ 11111111   (255, оно же −1)
= 100000110  → девятый бит отбрасываем →
  00000110   (6)

7 + 255 = 262, а 262 − 256 = 6. Сложение честно сработало как вычитание. Осталось довести эту идею до правила.

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

Правило чтения из этого определения простое:

• если старший бит равен 0 – число неотрицательное, читается как обычное беззнаковое;
• если старший бит равен 1 – число отрицательное, и чтобы получить его, из беззнакового чтения нужно вычесть $2^n$.

Например, байт 11111011 как беззнаковое – это 251. Старший бит единица, значит знаковое чтение: 251 − 256 = −5.

Старший бит и здесь работает признаком знака, но, в отличие от прямого кода, он не «отдельный флажок»: он остаётся полноценным разрядом со своим весом – просто вес этот отрицательный.

Это то же разложение по весам разрядов, что в уроке 2.4, с единственной правкой: вес старшего разряда взят с минусом. Для восьми битов веса получаются такие:

Возьмём 11111011: −128 + 64 + 32 + 16 + 8 + 0 + 2 + 1 = −5. Тот же ответ, что и через «251 − 256», – и получен обычным суммированием весов, без всяких «если».

Виджет ниже показывает оба чтения одновременно, и это главное, что стоит в нём заметить: строка «в памяти лежит» одна, набор битов один, а числа под ним – разные. Биты кликабельны; обратите внимание, что формулы в двух панелях отличаются ровно одним слагаемым – весом старшего разряда.

Что стоит попробовать:

• Нажмите «все единицы»: беззнаковое чтение – 255, знаковое – −1.
• Нажмите «максимум +» (127), а затем включите старший бит: число прыгнет с 127 на −128, хотя вы тронули всего один бит.
• Наберите любое положительное число и нажмите «инвертировать и +1» – это алгоритм из следующего раздела. Знаковое чтение сменит знак, а беззнаковое просто станет другим числом.
• Пока старший бит выключен, оба чтения совпадают – различия начинаются со 128.

Считать $2^n -$ |x| в столбик неудобно, поэтому на практике пользуются механическим правилом из трёх шагов. Запишем −5 в восьми битах:

1. Записать модуль числа в двоичном виде, дополнив нулями до нужной ширины: 5 → 00000101.
2. Инвертировать все биты (нули на единицы, единицы на нули): 11111010.
3. Прибавить единицу: 11111011.

Готово: −5 в восьмибитном дополнительном коде – это 11111011.

Почему это работает, видно из арифметики: инвертирование всех битов даёт 255 − |x|, а прибавление единицы – 256 − |x|, то есть в точности определение. Ровно поэтому шагов именно три, а не два.

Обратный перевод – из дополнительного кода в привычную запись – выполняется тем же самым алгоритмом: инвертировать биты и прибавить единицу. Возьмём 11111011: инвертируем → 00000100, прибавляем 1 → 00000101 = 5, а знак мы уже знаем по старшему биту, он был единицей. Значит, −5. Одна и та же процедура работает в обе стороны – приятное свойство, которое стоит запомнить.

Соберём в одну таблицу ключевые точки восьмибитного диапазона:

Три наблюдения по таблице:

• Ноль ровно один. Комбинация 10000000, которая в прямом коде была «минус нолём», здесь занята полезным числом −128. Проблема двух нулей исчезла сама.
• Диапазон несимметричен: от −128 до +127. Отрицательных чисел на одно больше, чем положительных, – как раз потому, что ноль занимает место в «положительной» половине, а освободившаяся от «минус нуля» комбинация ушла отрицательным. Это не недочёт, а прямое следствие того, что комбинаций 256 – число чётное, а ноль один.
• −1 – это все единицы. Байт 11111111 в знаковом чтении даёт −1. Удобный ориентир: если в отладчике видите «сплошные единицы» или значение 255 там, где ожидали небольшое отрицательное, – скорее всего, перед вами −1, прочитанная как беззнаковая.

Общее правило для n битов: диапазон знакового целого – от $-2^{n-1}$ до $2^{n-1} - 1$.

Числа 32 767 и 2 147 483 647 стоит просто узнавать в лицо: встретив такое значение в чужой программе или в описании формата файла, вы сразу понимаете, что речь о 16- или 32-битном знаковом целом.

Вернёмся к требованию «вычитание должно быть сложением» и проверим его на примере. Посчитаем 7 + (−5), сложив биты как обычные двоичные числа, без всякого разбора знаков:

   00000111   (7)
+  11111011   (−5, он же 251)
= 100000010

Девятый бит не вмещается в байт и отбрасывается – и остаётся 00000010, то есть 2. Правильный ответ, полученный обычным сложением.

Тот самый отброшенный бит и есть $2^8 = 256$, которое мы добавили в определении дополнительного кода. Оно вылетает за границу ячейки и исчезает – именно поэтому определение и выбрано таким.

Практический вывод, ради которого всё и делалось: процессору для вычитания не нужна отдельная схема. Чтобы вычесть, он переводит второе число в дополнительный код (инвертировать и +1 – обе операции элементарные) и складывает уже знакомым сумматором. Одна схема вместо двух, и никаких ветвлений по знакам. Именно поэтому дополнительный код используют практически все современные процессоры, а прямой код остался историей.

Кольцо никуда не делось – просто теперь его разрыв приходится на другое место. Прибавим единицу к максимуму:

01111111 (127) + 1 = 10000000, а это −128.

Прибавили единицу – и получили минимум диапазона. Число «перевернулось». В беззнаковом случае переполнение хотя бы выглядело безобидно (255 → 0), здесь же результат меняет знак, и заметить это гораздо труднее.

Коварство такой ошибки в том, что программа не падает и ничего не сообщает – она спокойно продолжает работать с неверным числом, и дальше по цепочке вычислений это выглядит как необъяснимая чепуха. В уроке 5.3 мы разберём реальную аварию, случившуюся ровно из-за такого переполнения при переводе вещественного числа в целое.

В уроке 5.1 мы уже предупреждали: в Python тип int не имеет фиксированной ширины, поэтому переполнения в нём не бывает – при нехватке места интерпретатор просто выделяет ещё байт. Значит ли это, что дополнительный код в Python не увидеть? Увидеть можно, и в двух местах.

Во-первых, функция bin() для отрицательного числа печатает не дополнительный код, а знак и модуль: bin(-5) даёт строку -0b101. Это удобно человеку, но к тому, как биты лежат в памяти, отношения не имеет.

Во-вторых, побитовые операции (весь блок 6) работают с отрицательными числами именно по правилам дополнительного кода, только с бесконечной цепочкой единиц слева вместо восьми битов. Поэтому, наложив маску & 0xFF, можно увидеть тот самый восьмибитный дополнительный код: -5 & 0xFF даёт 251.

А ещё фиксированная разрядность вернётся, как только вы выйдете за пределы «просто Python»: массивы NumPy (int8, int16, int32), упаковка данных модулем struct, любые бинарные форматы файлов и сетевые протоколы – всюду ширина задана жёстко, и всё сказанное в этом уроке применяется буквально.

Возвращаемся к вопросу из начала урока: куда девать минус, если все 256 комбинаций заняты? Ответ – никуда не девать. Мы не нашли новое место, а перераспределили те же 256 комбинаций: половину отдали отрицательным числам, и старший разряд получил отрицательный вес −128 вместо +128. Ни один бит на «знак» отдельно не потрачен.