Отрицательные числа в битах: дополнительный код и ширина слова

Если ты запишешь −5 в восьми битах, объяснишь, почему ~x равно -x - 1, и скажешь, чему равны 127 + 1 в восьмибитном знаковом типе и -7 >> 1, - листай до «Теперь сам».

Как думаешь, чему равно 100 + 100 в восьми битах со знаком

В переменной восемь битов, она хранит числа со знаком. В неё кладут сумму 100 + 100.

Прежде чем читать дальше, выбери: 200, 127 («упёрлось в потолок»), ошибка или что-то четвёртое? Ответ - четвёртое: −56. Ни ошибки, ни потолка: биты суммы честно посчитаны, но тот же набор битов, прочитанный как число со знаком, означает другое число.

На что это похоже

Счётчик пробега в старой машине - три колёсика с цифрами, от 000 до 999. Проехал километр после 999 - на счётчике 000: тысяча «не поместилась» и пропала. Теперь покрути его назад с нуля: 000, 999, 998. Если договориться, что 999 значит −1, а 998 значит −2, счётчик начинает уметь отрицательные числа, и ничего в его механике менять не пришлось. Проверка: −2 + 5 - это 998 и пять щелчков вперёд: 999, 000, 001, 002, 003. Получилось 3.

Договориться осталось об одном: где граница. Половину показаний, с 500 по 999, отдают отрицательным числам, с 000 по 499 - неотрицательным.

Механизм: слово, кольцо остатков и дополнение

Слово ширины n - это n битов, и ни одним больше. В нём помещается 2ⁿ разных наборов. Без знака их читают как числа от 0 до 2ⁿ − 1. Перенос из старшего разряда пропадает, то есть сложение идёт по модулю 2ⁿ - это арифметика остатков из прошлого раздела, с модулем 256 для восьми битов. Остатки удобно представлять расставленными по кругу, как часы на циферблате: за 2ⁿ − 1 снова идёт ноль. Дальше этот круг называется кольцом.

Дополнительный код - договорённость читать верхнюю половину кольца как отрицательные числа: набор битов со значением u без знака означает u, если старший бит ноль, и u − 2ⁿ, если старший бит единица.

биты        без знака    со знаком
0000 0000        0           0
0000 0001        1           1
0111 1111      127         127       наибольшее положительное
1000 0000      128        −128       наименьшее отрицательное
1111 1011      251          −5
1111 1111      255          −1

По модулю 256 числа 251 и −5 сравнимы: разница между ними - ровно 256. Поэтому сложение со знаком не требует отдельной схемы: процессор складывает биты, а знак - вопрос чтения.

Почему -x равно ~x + 1. Сложи x и ~x: в каждом разряде у одного ноль, у другого единица, сумма - n единиц подряд, то есть 2ⁿ − 1. Значит ~x = 2ⁿ − 1 − x, и ~x + 1 = 2ⁿ − x - как раз запись числа -x. Отсюда и формула из прошлого урока: ~x = -x - 1.

def v_slovo(x, n):
    return x & (1 << n) - 1

def so_znakom(u, n):
    if u >> n - 1 & 1:
        return u - (1 << n)
    return u

def bity(x, n):
    return bin(v_slovo(x, n))[2:].zfill(n)

print(bity(5, 8), bity(-5, 8), v_slovo(-5, 8))
print(bity(~5, 8), v_slovo(~5 + 1, 8))
print(so_znakom(251, 8), so_znakom(128, 8), so_znakom(255, 8))

00000101 11111011 251
11111010 251
-5 -128 -1

v_slovo вырезает n младших битов - делает то, что процессор делает сам. so_znakom читает вырезанное как число со знаком; запись u >> n - 1 & 1 в ней - это (u >> (n - 1)) & 1: вычитание выполняется раньше сдвига, и здесь это как раз нужно. У отрицательного числа в Python слева стоит бесконечный ряд единиц, поэтому -5 & 0xFF даёт те самые восемь битов 11111011.

Правило

В слове ширины n число со знаком лежит в пределах от −2ⁿ⁻¹ до 2ⁿ⁻¹ − 1. Запись числа -x - это 2ⁿ − x, она же ~x + 1. Старший бит равен единице ровно у отрицательных. Сложение, вычитание и умножение дают одни и те же биты для знакового и беззнакового чтения; результат, вышедший за пределы, заменяется числом, сравнимым с ним по модулю 2ⁿ. В Python слово получают маской x & ((1 << n) - 1).

Разбор: три сложения в восьми битах

print(so_znakom(v_slovo(5 - 7, 8), 8), bity(5 - 7, 8))
print(so_znakom(v_slovo(127 + 1, 8), 8), so_znakom(v_slovo(100 + 100, 8), 8))
print(v_slovo(200 + 100, 8), so_znakom(v_slovo(-(-128), 8), 8))

-2 11111110
-128 -56
44 -128

Первая строка - обычный случай: 5 − 7 = −2, в битах 11111110, то есть 254 без знака, и 254 − 256 = −2.

Вторая - переполнение: настоящий ответ не помещается в слово. 127 + 1 в битах - 01111111 + 1 = 10000000, а это −128: число перешло через границу половин кольца. 100 + 100 = 200, в битах 11001000, со знаком 200 − 256 = −56. Ответ из начала урока.

Третья строка: без знака 200 + 100 = 300, а 300 − 256 = 44. И последнее число - самое коварное: −(−128) равно −128. Положительного 128 в восьми битах со знаком нет, отрицательных на одно больше, чем положительных. Модуль наименьшего числа не представим, и функция «модуль числа» на нём возвращает отрицательное.

Разбор: сдвиг вправо, расширение и основание −2

Влево сдвиг один, а вправо их два, и различает их как раз чтение знака.

биты числа −8 в восьми битах:           1111 1000
логический сдвиг вправо на 1:           0111 1100   = 124     слева вдвигается ноль
арифметический сдвиг вправо на 1:       1111 1100   = −4      слева копируется знаковый бит

Логический годится для чисел без знака, арифметический - для чисел со знаком: он делит на два и сохраняет знак. В Python >> всегда арифметический: -8 >> 1 равно −4. Логический получают маской: (-8 & 0xFF) >> 1 равно 124.

Арифметический сдвиг округляет вниз, а не к нулю: -7 >> 1 равно −4, тогда как деление в C даёт -7 / 2 = −3. Заменить деление отрицательного числа сдвигом напрямую нельзя.

Расширение знака. Чтобы переложить число со знаком из 8 битов в 16, слева дописывают копии старшего бита: −5 - это 11111011 и 1111111111111011. Допишешь нули - получишь 251. Целое в Python - слово, расширенное до бесконечности.

Дополнительный код - не единственный способ обойтись без знака минус. В системе с основанием −2 веса разрядов - 1, −2, 4, −8, 16, и любое целое пишется нулями и единицами: 6 = 16 − 8 − 2 = 11010, −6 = −8 + 4 − 2 = 1110, −1 = −2 + 1 = 11. Знака нет вовсе, а положительные числа занимают нечётное число разрядов, отрицательные - чётное. Платить приходится сложением: перенос в следующий разряд идёт с обратным знаком, и 1 + 1 - это 110. В процессорах прижился дополнительный код - у него сложение обычное.

Что ломается без этого

Первое: переполнение молчит. Сумма двух положительных стала отрицательной - и программа пошла дальше. В C хуже: переполнение знакового типа объявлено неопределённым поведением, и компилятор вправе выкинуть проверку if (x + 1 < x) как заведомо ложную.

Второе: знаковое с беззнаковым. В C слово unsigned и суффикс u означают беззнаковый тип, i-- - уменьшение на единицу. Сравнение -1 < 1u ложно: −1 приводится к беззнаковому и становится наибольшим числом типа. Цикл for (unsigned i = n - 1; i >= 0; i--) не останавливается: беззнаковое всегда не меньше нуля, и после нуля идёт 2³² − 1.

Третье: байт со знаком. Байт 0xFF, прочитанный в знаковую переменную, - это −1; при расширении до 32 битов он превращается в 0xFFFFFFFF, а не в 0x000000FF. Так ломаются разбор двоичных файлов и индексы таблиц «по коду символа».

Четвёртое: отрицательный остаток. В Java и C хеш % размер бывает отрицательным, когда хеш отрицателен, и индекс уходит за начало таблицы. Лечится маской хеш & 0x7FFFFFFF до взятия остатка: это 31 единица, все биты слова, кроме знакового. В Python остаток по положительному модулю отрицательным не бывает.

Зачем это в работе

Хеш-функции и контрольные суммы описаны для 32-битных слов и рассчитывают на отбрасывание переноса. Переносишь такую функцию в Python - после каждого умножения и сложения ставь & 0xFFFFFFFF, иначе число растёт без предела и ответы расходятся с эталоном.

Формат сетевого пакета или файла говорит «знаковое 16-битное» - и два байта 0xFF 0xFE, старший первым, то есть 0xFF << 8 | 0xFE = 0xFFFE, надо прочитать как −2, а не как 65534. Это функция so_znakom из урока, в одну строку: (u ^ 0x8000) - 0x8000. ^ переворачивает знаковый бит, вычитание отнимает его вес: у числа со старшей единицей бит гаснет и вычитается 32 768, у числа без неё бит зажигается и тут же вычитается обратно.

Переполнение - источник настоящих уязвимостей: размер буфера, посчитанный как число * размер, переполняется, памяти выделяется мало, а пишется много. Поэтому в Rust переполнение в отладочной сборке останавливает программу, а в C компиляторы дают __builtin_add_overflow, и стандарт C23 закрепил то же под именем ckd_add.

Теперь сам

1. Запиши −20 в восьми битах и назови то же слово как число без знака.
2. Слово 1001 0110 - какое это число со знаком?
3. Чему равно ~0 и почему?
4. В 16 битах со знаком складывают 30000 и 10000. Что получится?
5. Чему равны -9 >> 1 и (-9 & 0xFF) >> 1?