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

Целое число в памяти компьютера занимает заранее известное количество битов: 8, 16, 32 или 64. Поэтому у него есть наименьшее и наибольшее значение. Отрицательные числа хранятся в дополнительном коде, а если результат не помещается в отведённые биты, случается переполнение: счёт идёт по кругу и начинается с другого конца.

Сколько разрядов, столько и чисел

Посмотрите на счётчик воды в квартире. Кубометры на нём показывают пять колёсиков с цифрами, и после 99 999 счётчик покажет 00 000: шестого колёсика нет. С числами в компьютере так же. Программа заранее выбирает, сколько байтов отвести числу, и больше разрядов у него не появится.

Если число не бывает отрицательным, его называют беззнаковым. Все сочетания битов тогда достаются числам от нуля и выше.

Как записать минус

Первое, что приходит в голову, — отдать левый бит под знак: 0 означает плюс, 1 — минус. Тогда 3 — это 00000011, а −3 — 10000011. Способ понятный, но неудобный.

Во-первых, нулей становится два: 00000000 и 10000000, «плюс ноль» и «минус ноль». Во-вторых, ломается сложение в столбик. Сложим 5 и −3:

  00000101     5
+ 10000011    −3: знак и тройка
  --------
  10001000    получилось −8, а должно быть 2

Процессору пришлось бы каждый раз проверять знаки и выбирать, складывать или вычитать. Нужна запись, при которой обычное сложение само даёт верный ответ.

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

Вернёмся к счётчику воды. Если на нём 00 000 и колёсики крутятся назад, следующим покажется 99 999. Значит, 99 999 можно считать записью числа −1: прибавьте единицу, и снова получатся нули.

В восьми битах роль «всех девяток» играют все единицы:

  11111111
+ 00000001
  --------
1 00000000    девятый бит не помещается и пропадает

Осталось 00000000. Раз 11111111 + 1 = 0, то 11111111 — это −1. Такую запись и называют дополнительным кодом.

Получить отрицательное число можно в два шага: инвертировать все биты, то есть заменить нули единицами, а единицы нулями, и прибавить единицу.

 5    00000101
      11111010    инвертировали
−5    11111011    прибавили 1

Тем же правилом число превращается обратно: инвертируем 11111011, прибавляем 1 и получаем 00000101.

Теперь сложим 5 и −3. Число −3 — это 11111101.

  00000101     5
+ 11111101    −3
  --------
1 00000010    девятый бит пропал, осталось 2

Ответ верный, хотя мы складывали как обычно и о знаках не думали. Причина вот в чём. Инверсия превращает число x в 255 − x, а после прибавления единицы получается 256 − x. Вместо −3 в памяти лежит 253. Прибавить 253 — то же самое, что отнять 3 и прибавить 256, а эти лишние 256 как раз и уносит девятый бит.

Читать такую запись можно и по весам разрядов. Нужно только считать, что левый разряд весит не 128, а −128:

11111011 = −128 + 64 + 32 + 16 + 8 + 2 + 1 = −5

Если левый бит равен 1, число отрицательное. Из 256 сочетаний половина досталась отрицательным числам, одно — нулю, а положительным осталось 127.

Переполнение: числа идут по кругу

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

У круга нет конца, но есть два «шва» — на схеме они отмечены пунктиром. Беззнаковые числа спотыкаются вверху: после самого большого идёт ноль. Знаковые — внизу: после самого большого положительного идёт самое маленькое отрицательное. Для восьми битов это выглядит так:

Без знака:    255 + 1 = 0        11111111 → 00000000
Со знаком:    127 + 1 = −128     01111111 → 10000000

Процессор при этом не останавливается: бит, который не поместился, просто отбрасывается. Следить за переполнением должна программа, и иногда об этом забывают.

• Pac-Man. В игре 1980 года номер уровня хранится в одном байте. Из-за переполнения 256-й уровень загружается с ошибкой: половину экрана занимает мешанина из знаков, и пройти его нельзя.
• Счётчик YouTube. В декабре 2014 года число просмотров клипа «Gangnam Style» превысило 2 147 483 647 — предел 32-битного числа со знаком. Инженеры заметили это заранее и перевели счётчик на 64 бита.
• Проблема 2038 года. Многие программы хранят время как число секунд, прошедших с начала 1970 года. Если это число 32-битное со знаком, оно закончится 19 января 2038 года в 03:14:07 по всемирному времени. Следующая секунда превратит его в отрицательное, и программа может решить, что на дворе декабрь 1901 года. Поэтому системы постепенно переводят на 64-битное время.

Частые вопросы

Как компьютер отличает −1 от 255?

Никак. В восьми битах оба числа записываются как 11111111. Сами биты не знают, есть ли у них знак: это решает программа, когда выбирает, как их читать.

Почему отрицательных чисел на одно больше?

Ноль занимает одно из сочетаний, которые начинаются с нулевого бита. Поэтому положительным числам достаётся 127 сочетаний, а отрицательным — все 128.

Левый бит — это и есть знак?

По нему виден знак, но остальные биты — не «само число». 10000001 — это −127, а не −1.

Коротко

• Целое число занимает фиксированное количество битов, поэтому его диапазон ограничен.
• Беззнаковое число из n битов лежит в пределах от 0 до 2ⁿ − 1.
• Отрицательные числа хранят в дополнительном коде: инвертируют биты и прибавляют 1.
• В дополнительном коде сложение работает одинаково для любых знаков; восемь битов вмещают числа от −128 до 127.
• При переполнении счёт идёт по кругу: 255 + 1 = 0 без знака и 127 + 1 = −128 со знаком.

С целыми числами разобрались. С дробными компьютеру ещё труднее — настолько, что он ошибается в простом примере: Дробные числа: почему 0,1 + 0,2 не равно 0,3.