Целые числа
Предпосылки: Двоичная система и байты.
← Двоичная система и байты | Побитовые операции →
Нули и единицы не имеют встроенного понятия знака: 00000101 — это 5, но как записать −5 теми же восемью битами? Компьютер должен как-то отличать положительное от отрицательного в рамках тех же двоичных комбинаций. Для этого придумали несколько схем — и не все из них выжили.
Числа без знака
Простейший случай — числа, которые не бывают отрицательными: возраст, количество элементов, адрес в памяти. Такие числа называются беззнаковыми (unsigned). Двоичная запись напрямую представляет значение: каждый бит — степень двойки, результат — их сумма. При n битах доступен диапазон от 0 до 2ⁿ − 1:
| Размер | Обозначение | Диапазон |
|---|---|---|
| 8 бит | u8 | 0 – 255 |
| 16 бит | u16 | 0 – 65 535 |
| 32 бита | u32 | 0 – 4 294 967 295 (~4.3 миллиарда) |
| 64 бита | u64 | 0 – 18 446 744 073 709 551 615 |
Обозначения вроде u8, u16, u32 — не привязаны к конкретному языку; это общепринятые сокращения для unsigned-типов соответствующей ширины.
Сложение в столбик
Сложение двоичных чисел без знака — та же операция, что и в предыдущей заметке. Разберём её подробнее на 8-битных числах, потому что этот же механизм лежит в основе знаковой арифметики.
Складываем 78 + 45 = 123:
78 = 01001110
45 = 00101101
переносы: 00011000
01001110 (78)
+ 00101101 (45)
----------
01111011 (123)
Справа налево, разряд за разрядом: 0+1 = 1. 1+0 = 1. 1+1 = 10 (пишем 0, перенос 1). 1+1+перенос 1 = 11 (пишем 1, перенос 1). 0+0+перенос 1 = 1. 0+1 = 1. 1+0 = 1. 0+0 = 0. Результат: 01111011 = 64+32+16+8+2+1 = 123.
Аппаратный сумматор в процессоре делает ровно это — обрабатывает перенос (carry — «перенос в следующий разряд») от младших разрядов к старшим. Одна и та же схема складывает любые числа фиксированной ширины — в том числе отрицательные, если правильно выбрать кодировку.
Знаковый бит: первая попытка
Самый очевидный способ обозначить знак — выделить старший бит: 0 = плюс, 1 = минус. Остальные биты — модуль числа. Такой формат называется знак-модуль (sign-magnitude, буквально «знак и величина»).
Для 3-битных чисел (1 бит знака + 2 бита модуля):
| Биты | Значение |
|---|---|
| 000 | +0 |
| 001 | +1 |
| 010 | +2 |
| 011 | +3 |
| 100 | −0 |
| 101 | −1 |
| 110 | −2 |
| 111 | −3 |
Диапазон: от −3 до +3 (для n бит: от −(2ⁿ⁻¹ − 1) до +(2ⁿ⁻¹ − 1)).
У формата два изъяна. Оба — не теоретические неудобства, а проблемы, которые удорожают железо.
Два нуля. 000 (+0) и 100 (−0) — разные битовые комбинации, но одно и то же число. Сравнение на ноль требует проверки двух значений вместо одного. Из 8 комбинаций (2³) одна потрачена впустую.
Сумматор не работает. Сложим (+1) и (−1) обычным сложением:
001 (+1)
101 (-1)
----
110 (-2) <-- неверно, должно быть 0
Результат −2, а не 0. Сумматор, который отлично складывает беззнаковые числа, даёт мусор на знаковых. Чтобы вычитать, нужна отдельная схема, которая сравнивает модули, вычитает меньший из большего и выбирает знак. Это дополнительные транзисторы, дополнительные стадии конвейера, дополнительная сложность. Если арифметику можно свести к одному сумматору — лучше.
Обратный код: вторая попытка
Если сложение в формате знак-модуль ломается, может, стоит по-другому кодировать отрицательные числа? Обратный код (ones’ complement — «дополнение до единиц») получает −x инвертированием всех битов числа x: каждый 0 становится 1, каждая 1 становится 0.
Для 3-битных чисел:
| Биты | Значение |
|---|---|
| 000 | +0 |
| 001 | +1 |
| 010 | +2 |
| 011 | +3 |
| 100 | −3 |
| 101 | −2 |
| 110 | −1 |
| 111 | −0 |
Сложение стало лучше. (+1) + (−1):
001 (+1)
110 (-1)
----
111 (-0)
−0 — технически ноль, но снова два нуля: 000 (+0) и 111 (−0). И ещё одна странность: если при сложении возникает перенос за пределы старшего бита, его нужно прибавить обратно к результату (end-around carry — «циклический перенос»). Для (+3) + (−1):
011 (+3)
+ 110 (-1)
-----
1001 (перенос за пределы 3 бит)
Отбрасываем перенос — получаем 001 (+1). Но нужно прибавить этот перенос обратно: 001 + 1 = 010 (+2). Верно. Правило работает, но каждое сложение может потребовать дополнительного шага. Два нуля по-прежнему тратят одну комбинацию впустую.
Обратный код — шаг в правильном направлении (сумматор почти работает), но не финальный ответ.
Дополнительный код
Главная идея — использовать модульную арифметику. Аналогия: одометр автомобиля с тремя разрядами показывает 000–999. Если от 000 вычесть 1, счётчик не уходит в минус — он перескакивает на 999. Для счётчика 999 и −1 неотличимы: прибавить 999 к любому числу и отбросить перенос — то же самое, что вычесть 1.
Перенесём идею на 8 бит. Восемь бит дают 256 комбинаций — как одометр от 000 до 255. Число −1 можно представить как 256 − 1 = 255 = 11111111. Прибавив 255 к любому числу в пределах 8 бит и отбросив перенос за пределы байта, получим то же, что при вычитании 1.
Этот формат называется дополнительный код (two’s complement — «дополнение до двойки», потому что −x вычисляется как 2ⁿ − x). Для 8-битного числа: −x = 256 − x.
Конкретный пример: −5 в 8-битном дополнительном коде.
256 - 5 = 251 = 11111011
Проверяем: 5 + (−5) должно дать 0.
переносы: 111111110
00000101 (5)
+ 11111011 (-5, = 251 беззнаково)
----------
100000000 (9 бит)
Девятый бит (перенос) выходит за пределы 8-битного регистра и отбрасывается. Оставшиеся 8 бит — 00000000 = 0. Сумматор, ничего не знающий о знаках, дал правильный результат.
Быстрый способ вычислить −x — «инвертировать и прибавить 1». Для −5:
5 = 00000101
--------
~5 = 11111010 (инвертировали все биты)
+1 = 11111011 (прибавили 1)
Результат: 11111011 = 251 беззнаково = −5 знаково. Тот же ответ, что и через 256 − 5. Почему этот трюк работает: инвертирование даёт (2ⁿ − 1 − x) — это обратный код, «дополнение до единиц». Прибавляем 1 — получаем 2ⁿ − x, то есть дополнительный код.
Три проблемы — три решения
Формат знак-модуль имел два нуля, требовал отдельной схемы вычитания и терял одну комбинацию. Дополнительный код решает все три:
Один ноль. 00000000 = 0. Значение 10000000 тоже не тратится на второй ноль — оно представляет −128.
Один сумматор. Та же схема, которая складывает беззнаковые числа, правильно складывает и знаковые в дополнительном коде. Не нужна отдельная аппаратная схема для вычитания — процессор вычитает через сложение: a − b = a + (−b). Вычислить −b — инвертировать биты и прибавить 1 — дешёвая операция.
Ни одна комбинация не пропадает. 256 комбинаций = 256 различных чисел. Ни одна не дублирует другую.
Круг значений
Значения дополнительного кода удобно представить как круг — тот же одометр. Для 8 бит:
0 (00000000)
/ \
-1 / \ 1
(11111111) | | (00000001)
| |
-2 | | 2
(11111110) | | (00000010)
\ ... /
\ /
-128 ... 127
(10000000) (01111111)
Верхняя точка — 0. По часовой стрелке — положительные числа до 127. Дальше — переход к −128, и вверх по кругу через −127, −126, …, −1 обратно к нулю. Прибавление единицы — шаг по часовой стрелке. Вычитание — против. Сумматор просто «крутит» этот круг, не различая знаковые и беззнаковые числа.
Диапазон и асимметрия
Для n бит в дополнительном коде диапазон: от −2ⁿ⁻¹ до 2ⁿ⁻¹ − 1.
| Размер | Тип | Минимум | Максимум |
|---|---|---|---|
| 8 бит | i8 | −128 | 127 |
| 16 бит | i16 | −32 768 | 32 767 |
| 32 бита | i32 | −2 147 483 648 | 2 147 483 647 |
| 64 бита | i64 | −9 223 372 036 854 775 808 | 9 223 372 036 854 775 807 |
Обозначения i8, i16, i32, i64 — общепринятые сокращения для знаковых (signed) целых соответствующей ширины.
Диапазон несимметричен: отрицательных значений на одно больше, чем положительных. Причина — ноль занимает одну комбинацию из «положительной» половины (старший бит = 0). Комбинация 10000000 (для 8 бит) не нужна ни для +0, ни для −0 — она свободна и достаётся числу −128.
Практическое следствие: выражение −x не всегда помещается в тот же тип. Для i8: −(−128) = 128, но максимум i8 — 127. Инвертирование минимального значения приводит к переполнению.
Переполнение
Что происходит, когда результат не помещается в отведённые биты?
Беззнаковое переполнение. u8: 255 + 1. Двоичное сложение:
11111111 (255)
+ 00000001 (1)
----------
100000000 (256 = 9 бит)
Девятый бит отбрасывается — остаётся 00000000 = 0. Счётчик совершил полный оборот. 255 + 1 = 0. Это не ошибка процессора — он просто отбрасывает бит, который не влезает. Результат всегда равен (a + b) mod 2ⁿ.
Знаковое переполнение. i8: 127 + 1. Двоичное сложение:
01111111 (127)
+ 00000001 (1)
----------
10000000 (-128 в дополнительном коде)
Перенос не выходит за пределы 8 бит, но старший бит стал 1 — при знаковой интерпретации это −128. Шаг по часовой стрелке от 127 попадает на −128 — противоположный конец круга. Результат арифметически неверен: 127 + 1 ≠ −128.
Для вычитания — симметрично. i8: −128 − 1:
10000000 (-128)
+ 11111111 (-1)
----------
101111111 (отбрасываем перенос -> 01111111 = 127)
−128 − 1 = 127. Шаг против часовой стрелки от −128 попадает на 127.
Переполнение — причина реальных инцидентов. 4 июня 1996 года первый запуск ракеты Ariane 5 закончился взрывом через 37 секунд после старта. Бортовой компьютер конвертировал 64-битное значение горизонтальной скорости в 16-битное знаковое целое. Значение превысило 32 767 — произошло переполнение, навигационная система получила бессмысленные данные, и ракета отклонилась от курса.
Стандартные ширины
Выбор ширины определяет, когда наступит переполнение: чем шире тип, тем дальше граница. Современные процессоры предлагают фиксированный набор ширин:
| Бит | Знаковый | Диапазон знакового | Беззнаковый | Диапазон беззнакового |
|---|---|---|---|---|
| 8 | i8 | −128 .. 127 | u8 | 0 .. 255 |
| 16 | i16 | −32 768 .. 32 767 | u16 | 0 .. 65 535 |
| 32 | i32 | −2 147 483 648 .. 2 147 483 647 | u32 | 0 .. 4 294 967 295 |
| 64 | i64 | ~−9.2 × 10¹⁸ .. ~9.2 × 10¹⁸ | u64 | 0 .. ~1.84 × 10¹⁹ |
8-битный диапазон (0–255) покрывает символы, яркость пикселей, флаги. Для счётчиков и идентификаторов его не хватает — 32-битный тип вмещает до ~4 миллиардов значений и остаётся основным рабочим типом. Когда и этого мало — адреса памяти на современных машинах, временные метки, финансовые суммы в копейках — используют 64-битный.
Ширину выбирают по диапазону значений задачи: u8 для яркости пикселя (0–255), i32 для населения города, u64 для уникальных идентификаторов. Слишком узкий тип — переполнение. Слишком широкий — расход памяти и потенциально более медленный доступ на некоторых архитектурах.
Целое число — цепочка битов фиксированной длины. Иногда нужно работать не с числом целиком, а с конкретным битом: проверить, установлен ли флаг, замаскировать часть адреса, объединить несколько флагов в одно число. Для этого существуют побитовые операции.
Sources
- Patterson, D., Hennessy, J., 2013, Computer Organization and Design. 5th ed. Morgan Kaufmann.
- Petzold, C., 2000, Code: The Hidden Language of Computer Hardware and Software. Microsoft Press.
- Lions, J. L., et al., 1996, Ariane 5 Flight 501 Failure Report. ESA/CNES.