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

Если ты разложишь сложение на ^ и &, запишешь среднее двух чисел без промежуточной суммы и скажешь, по какому признаку видно переполнение знакового сложения, - листай до «Теперь сам».

Как думаешь, что не так с серединой отрезка

Двоичный поиск ищет в массиве, границы отрезка - lo и hi, середина - (lo + hi) / 2. Обе границы - правильные индексы, середина лежит между ними. Числа 32-битные со знаком.

Прежде чем читать дальше, попробуй угадать, при каком размере массива эта строка даст отрицательный индекс. Ответ: когда элементов больше 2³⁰, около миллиарда. lo и hi помещаются в слово каждое, а их сумма - уже нет.

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

Сложение столбиком, как в школе. В каждом разряде делаются две вещи: пишется цифра суммы и запоминается «один в уме». Обычно их делают вперемешку, справа налево. Но можно разделить: сначала пройти по всем разрядам и написать только цифры, не обращая внимания на переносы. Потом отдельной строкой выписать все «в уме», сдвинув их на разряд влево. И сложить эти две строки - тем же способом.

В двоичной системе обе вещи оказываются знакомыми операциями: цифра суммы двух битов без переноса - это ^, а перенос возникает только когда оба бита единицы - это &.

Механизм: сумма без переноса, перенос и признак по знакам

    a      =  0111        7
    b      =  0001        1
    a ^ b  =  0110        сумма без переносов
    a & b  =  0001        где возник перенос
перенос << 1  =  0010     он принадлежит следующему разряду

Тождество: a + b = (a ^ b) + ((a & b) << 1). Справа снова сложение, но более простое: единиц в переносе обычно меньше. Повторяя разложение, доходим до нулевого переноса.

круг    a       b (перенос)
 0     0111    0001
 1     0110    0010
 2     0100    0100
 3     0000    1000
 4     1000    0000        ответ 8

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

Из тождества получается среднее без переполнения. Раздели обе части на два: (a + b) / 2 = (a ^ b) / 2 + (a & b). Перенос уже был сдвинут влево, деление на два возвращает его на место. Итог - (a & b) + ((a ^ b) >> 1): общие биты двух чисел плюс половина различающихся. Сумма a + b нигде не вычисляется, и переполняться нечему.

Переполнение по знакам. Сумма положительного и отрицательного всегда лежит между ними и помещается в слово. Переполнение возможно, только когда знаки слагаемых одинаковы, - и тогда оно видно по тому, что знак результата другой. В битах: старший бит s отличается и от старшего бита a, и от старшего бита b, то есть старший бит числа (a ^ s) & (b ^ s) равен единице. У чисел без знака признак проще: сумма, потерявшая перенос из старшего разряда, меньше каждого из слагаемых.

Правило

a + b = (a ^ b) + ((a & b) << 1). Среднее с округлением вниз без промежуточной суммы: (a & b) + ((a ^ b) >> 1); для неотрицательных lo ≤ hi годится и lo + (hi - lo) / 2. Знаковое сложение s = a + b переполнилось тогда и только тогда, когда (a ^ s) & (b ^ s) отрицательно. Беззнаковое - когда s < a.

Разбор: сложение без плюса

def slozhit(a, b):
    krugov = 0
    while b != 0:
        perenos = a & b
        a = a ^ b
        b = perenos << 1
        krugov = krugov + 1
    return [a, krugov]

print(slozhit(5, 3), slozhit(12, 10), slozhit(7, 1), slozhit(255, 1), slozhit(170, 85))

[8, 4] [22, 2] [8, 4] [256, 9] [255, 1]

Функция рассчитана на неотрицательные числа: у отрицательного в Python бесконечный ряд единиц слева, и перенос уходил бы по нему без конца. 255 + 1 - девять кругов: перенос идёт через все восемь единиц. 170 + 85 - это 1010 1010 + 0101 0101: ни в одном разряде нет двух единиц, переносов нет вовсе, и ^ сразу даёт ответ. Такое сложение ничем не отличается от |.

Сто пар случайных 31-битных чисел дают в сумме 534 круга - 5,34 на пару, самое большее десять. Длинная цепочка переноса требует, чтобы много разрядов подряд «передавали» перенос дальше, и вероятность этого падает вдвое с каждым разрядом; поэтому среднее близко к логарифму ширины слова - для 31 бита это пять.

Разбор: середина отрезка в 32 битах, и что делать с умножением

Чтобы увидеть переполнение в Python, результат приводят к 32-битному слову со знаком - как в главе про дополнительный код.

def slovo32(x):
    x = x & 0xFFFFFFFF
    return (x ^ 0x80000000) - 0x80000000

def perepolnenie(a, b):
    s = slovo32(a + b)
    return ((a ^ s) & (b ^ s)) >> 31 & 1

a = 2000000000
b = 2100000000
print(slovo32(a + b), slovo32(a + b) // 2, perepolnenie(a, b))
print(a + (b - a) // 2, (a & b) + ((a ^ b) >> 1))
print(perepolnenie(2000000000, 100000000), perepolnenie(-2000000000, -200000000), perepolnenie(1, -1))

-194967296 -97483648 1
2050000000 2050000000
0 1 0

Сумма двух индексов около двух миллиардов превратилась в −194 967 296, середина - в отрицательный индекс. Обе безопасные формулы дают 2 050 000 000. Третья строка: два положительных, помещающихся в сумме, - переполнения нет; два отрицательных с суммой меньше −2³¹ - есть; разные знаки - не бывает.

Строка (lo + hi) / 2 стояла в java.util.Arrays.binarySearch. Ошибку заметили через девять лет после выхода библиотеки, когда массивы на миллиард элементов стали помещаться в память. В Python целое не переполняется, и (lo + hi) // 2 из урока про двоичный поиск верна. В C, Java, Go и Rust пишут lo + (hi - lo) / 2.

Граница приёмов - умножение. Признака по знакам у него нет: произведение может переполниться много раз и вернуться к правдоподобному числу. 65536 · 65536 в 32 битах - ровно ноль, 46341 · 46341 - −2 147 479 015, хотя 46340² ещё помещается. Проверить умножение можно тремя способами: посчитать в типе вдвое шире; сравнить до умножения - если a > наибольшее // b, произведение не поместится (46341 > 2 147 483 647 // 46341 = 46340); или вызвать готовую проверку - в C это __builtin_mul_overflow, в C23 ckd_mul.

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

Первое: проверка после переполнения в C. if (a + b < a) для знаковых чисел компилятор вправе упростить: знаковое переполнение не определено, значит «его не бывает», и условие превращается в b < 0. Проверять нужно до сложения: a > INT_MAX - b, где INT_MAX - наибольшее значение типа.

Второе: среднее со знаком. lo + (hi - lo) / 2 верно, пока разность hi − lo помещается в слово. Для неотрицательных индексов это всегда так, а разность двух чисел разных знаков может переполниться сама. Формула с & и ^ верна для любых знаков.

Третье: размер из произведения. Память под n элементов по k байтов - это n * k. Если произведение переполнилось, выделится маленький блок, а записано будет много. Так устроена большая часть уязвимостей «переполнение целого».

Четвёртое: счётчик, который обернулся. 32-битный счётчик миллисекунд переполняется через 49,7 суток, счётчик секунд со знаком с 1970 года - в январе 2038-го. Программа работает месяц и ломается на втором.

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

Насыщающая арифметика: в обработке звука и изображений переполнение должно не оборачиваться, а упираться в край. Яркость 200 плюс 100 - это 255, а не 44. Переполнение ловят одним из способов выше и подставляют границу - без ветвления, маской из прошлого урока.

Длинная арифметика из раздела про числа складывает разряды по одному и передаёт перенос - там «один в уме» из аналогии существует буквально, как переменная. А аппаратный сумматор и объясняет, почему побитовые операции считаются самыми дешёвыми: у них нет цепочки переноса, все разряды готовы одновременно.

Проверка индексов и размеров на входе программы - длина пакета, число записей в файле, смещение - всегда включает проверку на переполнение суммы и произведения. Rust и Swift делают её в отладочной сборке сами, в C её пишут руками.

Теперь сам

1. Разложи 6 + 3 на сумму без переноса и перенос. Сколько кругов понадобится?
2. Найди среднее 10 и 14 по формуле (a & b) + ((a ^ b) >> 1).
3. В восьми битах со знаком: 100 + 50. Какие знаки у слагаемых и у результата и что это значит?
4. При каких lo и hi формула lo + (hi - lo) / 2 сама переполняется?
5. Сколько кругов сделает slozhit(1023, 1) и slozhit(1024, 1)?