Числа в памяти компьютера: коды, диапазоны и точность

Программа для карманных расходов сложила 0,1 и 0,2 рубля — и насчитала 0,30000000000000004. Не баг и не сломанный телефон: так честно отвечает память компьютера, в которой нет ни запятых, ни минусов, ни цифр — только нули и единицы в ячейках фиксированного размера. От того, как число уложено в биты, зависит и диапазон значений, и точность дробей, и то, почему сумма двух плюсов вдруг становится минусом. Разберёмся по порядку: сначала целые числа, потом дробные. Это не абстракция про железо: на ОГЭ спрашивают, влезет ли число в ячейку и что покажет переполнение, а в Python та же память лежит под каждой переменной.

Без знака: вся ячейка работает на число

Простейший договор — беззнаковое представление: все биты ячейки отдаются самому числу, и записать минус невозможно. В восьми битах 256 разных комбинаций: числа от 0 до 255. Число 77 в двоичной записи — это 01001101, а максимум 255 — восемь единиц подряд: 11111111. Попробуй прибавить ещё единицу: старший разряд не влезает, и ячейка обнуляется — 255 + 1 = 0. Это не ошибка, а следствие фиксированного размера: счётчик ведёт себя как одометр старой машины, который после 999 999 снова показывает нули. Кстати, восьми бит хватает на код одного символа: в таблице Windows-1251 ровно 256 позиций, от пробела до «я». В шестнадцати битах без знака влезает от 0 до 65 535 — столько, например, существует разных кодов символов Unicode и номеров портов.

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

Когда нужны минусы, старший бит объявляют знаковым: 0 — плюс, 1 — минус. Так устроен прямой код: у числа 52 модуль в двоичной записи 00110100, у минус пятидесяти двух — тот же модуль, но со старшей единицей: 10110100. Разница между 00000101 и 10000101 — только старший бит: это +5 и -5 в прямом коде. Красиво, но на практике прямой код неудобен. Во-первых, нуль получает два вида: 00000000 и 10000000 — «плюс нуль» и «минус нуль», хотя это одно и то же число. Во-вторых, сложение со знаком ломается: чтобы сложить 12 и -52, пришлось бы отдельно сравнивать модули, решать, чей знак победит, и вычитать меньший модуль из большего — процессор так не умеет, ему нужен один механизм для всех случаев.

Поэтому придумали обратный код: у отрицательного числа инвертируют все биты модуля, кроме знакового, — нули становятся единицами и наоборот. Финальный штрих — дополнительный код: к обратному прибавляют единицу. Выигрыш огромный: вычитание превращается в обычное сложение, знак отдельно обрабатывать не нужно, а нуль остаётся один. Чтобы вычесть 52, процессор прибавляет его дополнительный код — и получает верный результат, будто и не вычитал. Прогон: 12 плюс дополнительный код -52 даёт 00001100 + 11001100 = 11011000, а это -40 — ровно 12 - 52. Никакой отдельной логики для минуса не понадобилось. Честность кода проверяется на месте: число и его дополнительный код в сумме дают нуль с отброшенным переносом.

Алгоритм стоит прогнать второй раз на другом числе — рука должна делать его без пауз. Берём -37. Модуль 37 раскладывается по степеням двойки как 32 + 4 + 1, в восьми битах это 00100101. Прямой код: старший бит ставим в единицу — 10100101. Обратный код: переворачиваем все семь бит модуля, получаем 11011010. Дополнительный: прибавляем единицу — 11011011. Проверка занимает одну строку: эти биты без знака означают 128 + 64 + 16 + 8 + 2 + 1 = 219, а 219 - 256 = -37. Если проверка не сошлась, возвращайся к инверсии: чаще всего забывают переворачивать ведущие нули записи, трогая только биты в середине. Второе частое место ошибки — разложение модуля: выпиши степени двойки на черновике и складывай их с контролем, а не по памяти.

Почему положительных чисел на одно меньше? Разложи все 256 кодов по группам. Нуль — один: запись 00000000. Из семи бит модуля собирается 128 комбинаций, но одна из них занята нулём, на положительные числа остаётся 127: от 1 до 127. Отрицательные кодируются иначе: код -1 — это 11111111, код -2 — 11111110, и так по убыванию до записи 10000000, которой среди положительных пары не нашлось. Ей и присвоили значение -128. Итого кольцо из 256 кодов поделилось ровно: один нуль, 127 плюсов и 128 минусов — отсюда несимметрия диапазона. Тот же расклад в любой разрядности: у 16 бит минимум -32 768 при максимуме 32 767, у 32 бит — от -2 147 483 648 до 2 147 483 647. Разница всегда ровно в единицу, и ответ на вопрос «почему» один: нуль отнял место у положительных.

Переполнение — самая коварная ошибка арифметики: слагаемые были вполне нормальными, а сумма не влезла. Сложим в знаковом байте 100 и 50: честный ответ 150, но диапазон кончается на 127. Биты суммы 10010110 процессор читает по правилам дополнительного кода — и получает -106. Признак переполнения простой: плюс с плюсом дал минус или минус с минусом дал плюс. Поэтому счётчики в серьёзных программах держат в 32- и 64-битных ячейках с огромным запасом, а на ОГЭ про границу спрашивают напрямую: влезет ли результат в ячейку. Коварство в том, что программа не останавливается: она честно продолжает считать бессмыслицу, и заметить это может только человек, прикинувший масштаб чисел заранее.

Почему 0,1 + 0,2 не равно 0,3

Дробные числа компьютер хранит не как десятичные дроби, а в плавающей точке: число раскладывают на мантиссу — значащие цифры — и порядок, то есть степень двойки. Главная неожиданность ждёт здесь: дробь 0,1 в двоичной системе — бесконечная периодическая, как 1/3 в десятичной (0,3333...): и никакая честная ячейка не удержит бесконечный хвост. Десятичная система мучается с третью, двоичная — с 0,1 и 0,2, у которых хвост тоже не кончается. Бесконечный хвост в конечную ячейку не уложить, компьютер обрезает его по разрядной сетке и хранит не ровно 0,1, а ближайшее двоичное приближение. У 0,2 своё приближение, у их суммы — своё. Поэтому команда print(0.1 + 0.2) в Python честно печатает то, что лежит в ячейках: 0.30000000000000004. Целые числа от всего этого страдают нисколько — их биты точны.

Подсказка: клавиши J — следующая тема, K — предыдущая, на телефоне: свайп влево/вправо — соседняя тема