Целые числа и дополнительный код

Почему минус один это все единицы, что на самом деле происходит при переполнении и зачем у каждой целочисленной операции в Rust четыре версии. Урок, после которого i8::MIN.abs() перестаёт быть сюрпризом.

Идея

Начнём с программы, которая обязана работать, но паникует:

let x: i8 = i8::MIN;
println!("{}", x.abs()); // паника: attempt to negate with overflow

Модуль числа. Операция из пятого класса. Падает. Чтобы понять почему, нужно знать две вещи: как именно знаковые числа закодированы в битах и что Rust делает, когда результат не влезает в тип. Это и есть весь сегодняшний урок, и оба ответа тянутся из одного места.

Кодировка называется дополнительный код, и главное в ней не формула, а причина. Это не соглашение в духе «договоримся, что старший бит означает минус». Это трюк, благодаря которому процессору не нужны отдельные схемы для знаковой и беззнаковой арифметики: одно и то же железо складывает i32 и u32, разница существует только в голове компилятора. Базовую механику ты видел в уроке про биты и кодирование, сегодня доведём её до уровня, на котором проектируют АЛУ эмулятора и считают деньги без сюрпризов.

Дополнительный код

Выведем кодировку из одного требования: пусть сложение работает одинаково для всех чисел, без отдельного случая для отрицательных. Тогда минус один это такой байт, который при прибавлении единицы даёт ноль. Смотри:

  1111 1111
+ 0000 0001
-----------
1 0000 0000

Девятый бит не помещается в байт и отбрасывается, остаётся ноль. Значит, 1111 1111 и есть минус один. Никакой магии: минус один это все единицы просто потому, что плюс один превращает их в ноль.

Тот же результат даёт взгляд через веса разрядов, и он удобнее для расшифровки руками. В беззнаковом байте веса разрядов это 128, 64, 32, 16, 8, 4, 2, 1. Дополнительный код меняет ровно одно: вес старшего разряда становится отрицательным, минус 128. Проверим на минус единице: все восемь бит единицы, сумма весов минус 128 плюс 127 даёт минус 1. Сошлось.

Из отрицательного веса старшего бита следует вся арифметика типа:

i8:  от -128 (1000 0000) до 127 (0111 1111)
u8:  от 0    (0000 0000) до 255 (1111 1111)

Старший бит играет роль знака: если он установлен, отрицательный вес перевешивает всё остальное, число отрицательное. Поэтому арифметический сдвиг из прошлого урока копирует именно его: сохранить старший бит значит сохранить знак.

Практический способ закодировать минус икс, тот самый из учебников: инвертировать все биты и прибавить единицу. В Rust это в точности оператор унарного минуса:

let x: i8 = 5;          // 0000 0101
let inverted = !x;      // 1111 1010, это -6
let negated = !x + 1;   // 1111 1011, это -5
assert_eq!(negated, -x);

Почему работает: x + !x это все единицы, то есть минус один, откуда !x + 1 == -x. А почему инверсия без прибавления даёт -x - 1, теперь тоже видно из той же строчки.

И вот первая встреча с виновником вступления. Диапазон i8 несимметричен: минимум минус 128, максимум 127. Ноль занял одну из комбинаций в положительной половине, и у минимума нет положительной пары. -i8::MIN должен быть 128, а 128 в i8 не существует: инверсия и плюс один возвращают те же 1000 0000. Минус от минимума это минимум, молча, на уровне битов. Rust отказывается делать вид, что это нормально, и паникует; что именно значит «паникует» и когда, разберём прямо сейчас.

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

Договоримся о слове. Переполнение это когда настоящий, математический результат не влезает в тип: 200 плюс 100 в u8, минус от i8::MIN, умножение двух миллиардов в i32.

Что делает железо, ты уже видел в выводе минус единицы: складывает все биты честно, а те, что не поместились, отбрасывает. Результат получается по модулю 2 в степени N. Это не ошибка процессора и не его лень, это определение операции: сумматор работает в кольце остатков, и для криптографии, хешей или счётчиков такое поведение не баг, а ровно то, что заказывали.

Беда в том, что для большинства программ заворот это именно баг: количество товара не бывает минус 56, баланс не должен обнуляться от большого пополнения. Языки отвечают на это по-разному, и спектр поучителен. C объявляет знаковое переполнение неопределённым поведением: компилятор вправе считать, что его не бывает, и оптимизировать соответственно, поэтому программа с переполнением может сделать вообще что угодно. JavaScript не переполняется, потому что складывает в float, зато теряет точность. Rust выбирает третий путь: поведение строго определено, но определено как ошибка.

Точные правила такие. В debug-сборке арифметическое переполнение вызывает панику с внятным сообщением: ты встречал её на сдвигах в прошлом уроке и сейчас в abs. В release-сборке проверки сняты ради скорости, и значение заворачивается по модулю, как в железе. Важно, что и второй вариант это не неопределённое поведение в смысле C: результат точно известен, компилятор не имеет права ничего «оптимизировать» исходя из невозможности переполнения. Программа с заворотом в release неправильна ровно настолько, насколько неправильна её логика, но она детерминирована.

Развилкой управляет флаг overflow-checks в профиле сборки:

[profile.release]
overflow-checks = true

Включить проверки в release стоит почти всегда, кроме измеренно горячего кода: цена обычно единицы процентов, а молчаливый заворот в проде стоит дороже. Но и паника не решение, а лишь громкая констатация: «здесь баг». Настоящее решение это выбрать поведение явно, и для этого у каждого целочисленного типа есть четыре семейства методов.

Четыре семейства операций

У каждой арифметической операции в Rust, помимо оператора, есть четыре именованных версии. На примере сложения:

let x: u8 = 250;

assert_eq!(x.wrapping_add(10), 4);             // заворот по модулю
assert_eq!(x.checked_add(10), None);           // Option: None при переполнении
assert_eq!(x.saturating_add(10), 255);         // прилипание к границе
assert_eq!(x.overflowing_add(10), (4, true));  // значение плюс флаг

То же семейство есть у sub, mul, neg, abs, shl и остальных. Выбор между ними это не вопрос вкуса, у каждого своя предметная область, и полезно знать все четыре в лицо.

wrapping_ говорит: заворот по модулю это моя математика, так задумано. Хеш-функции и криптопримитивы живут в кольце по модулю и состоят из wrapping-умножений. Эмулятор обязан воспроизводить заворот настоящего процессора: программный счётчик, дошедший до конца адресного пространства, переходит в ноль, и wrapping_add здесь не обходной манёвр, а спецификация. Кольцевой буфер, счётчик секунд, индекс в таблице по модулю, всё это wrapping. Если wrapping-операций подряд много, есть обёртка std::num::Wrapping<T>, внутри которой обычные операторы заворачивают.

checked_ возвращает Option и заставляет обработать переполнение как ошибку. Это выбор для всего, где заворот означал бы тихую порчу данных: деньги, количества, размеры, любая бизнес-арифметика. Option соединяется с механикой урока про ошибки: оператор ? досрочно вернёт None, а ok_or превратит его в Result с нормальным описанием.

fn total_kopecks(price: u64, qty: u64) -> Option<u64> {
    price.checked_mul(qty)
}

saturating_ прилипает к ближайшей границе: всё, что выше максимума, становится максимумом, ниже минимума, минимумом. Это математика регуляторов и индикаторов: громкость, яркость, прогресс, координата на экране, уровень здоровья в игре. Везде, где «больше некуда» осмысленнее, чем «лопнуло», бери saturating и не пиши руками if x > MAX.

overflowing_ возвращает пару: завёрнутое значение и флаг, было ли переполнение. На первый взгляд экзотика, но именно так устроено железо: процессор после каждого сложения выставляет флаг переноса. Поэтому overflowing это инструмент двух ремёсел: многословной арифметики, где перенос из младшего слова уезжает в старшее (так устроены 256-битные числа в криптографии и в EVM), и эмуляции, где после каждой операции АЛУ нужно выставить флаги статуса. В блоке про эмулятор строчка let (result, carry) = a.overflowing_add(b) станет сердцем процессора.

Сводная шпаргалка, к которой стоит возвращаться, пока не осядет:

И заметь, как сюда встраивается философия урока про идиомы: голый + в Rust это утверждение «переполнение здесь невозможно, иначе это баг». Каждое именованное семейство переносит решение из комментария в сигнатуру, читатель видит семантику без контекста.

Расширение и усечение

Остался последний сюжет: что происходит с битами при преобразовании между целыми типами разной ширины и знаковости. Инструмент ты знаешь с второго урока, это оператор as, и там же ты чинил его самый известный фокус, усечение. Теперь объясним все его фокусы через дополнительный код.

Правил у as для целых ровно три, и все три механические:

// 1. Сужение отбрасывает старшие биты, остаются младшие
assert_eq!(300u16 as u8, 44);     // 300 = 0x012C, остался 0x2C
assert_eq!(-1i16 as u8, 255);     // 0xFFFF, остался 0xFF

// 2. Расширение знакового типа копирует знаковый бит
assert_eq!(-1i8 as i32, -1);      // 0xFF превратился в 0xFFFFFFFF

// 3. Расширение беззнакового заполняет нулями
assert_eq!(255u8 as i32, 255);    // 0xFF превратился в 0x000000FF

Сужение это в точности усечение по модулю: остаются младшие биты, и 300 в байте становится 44 без предупреждений. Расширение знакового типа называется знаковым расширением: старший бит копируется во все новые разряды, иначе минус один перестал бы быть минус единицей. Расширение беззнакового заполняет новые разряды нулями. А смена знаковости при той же ширине, i8 as u8, вообще не трогает биты, меняется только интерпретация: те же 1111 1111 были минус единицей, стали 255.

Отдельной строкой про float: f64 as i32 с версии 1.45 насыщает, всё что больше i32::MAX становится i32::MAX, NaN превращается в ноль. До той версии это было неопределённое поведение, и его ликвидация хорошая иллюстрация отношения Rust к молчаливым операциям.

Теперь оценка инструмента. as для целых никогда не паникует и никогда не врёт на уровне битов, но он молчалив: усечение и смена знака происходят без единого предупреждения, и при рефакторинге, когда ширина типа слева или справа меняется, as продолжает компилироваться с новым смыслом. Поэтому иерархия выбора такая, и она прямо продолжает урок про стандартные трейты:

let small: u8 = 200;

// расширение без потерь: From, существует только для безопасных направлений
let wide: u32 = u32::from(small);

// сужение: TryFrom, честный Result вместо молчаливого усечения
let back: u8 = u8::try_from(70000u32).unwrap_or(u8::MAX);

From между целыми реализован только там, где потерь не бывает в принципе, u8 в u32, i16 в i64; направление с потерями просто не скомпилируется. TryFrom покрывает остальные и возвращает Result. Ниша as после этого сужается до мест, где усечение и есть намерение: вырезать младший байт хеша, сложить половины слова в декодере, преобразовать после маски, когда влезание очевидно из кода строкой выше. Там as уместен и идиоматичен; везде, где значение приходит из данных, бери try_from.

Практика

Семейства операций запоминаются не таблицей, а ситуацией, в которой каждое из них спасает. Две задачи прямо в браузере: деньги, которым нужен checked_, и регулятор, которому нужен saturating_.

ДЗ

Дальше

С целыми числами разобрались до дна: биты, веса, заворот, четыре семейства. Осталась вторая половина числового мира, и она устроена совсем иначе. В следующем уроке разберём IEEE-754: почему 0.1 плюс 0.2 не равно 0.3, что такое NaN и денормали, и почему f64 не годится для денег, но прекрасно годится для физики.