Давайте вычислим среднее значение двух целых чисел и вернем среднее значение как INT. Обычный подход - целочисленное деление двух целых чисел и получение floor значения результата с плавающей запятой.

avg = floor((a + b) / 2)

Но если есть, то эти два значения: INT_MAX для C\C++ или std::i32::MAX в Rust; это вызовет переполнение.

Компилятор Rust покажет следующее:

поток «основной» запаниковал из-за «попытки добавить с переполнением»,

Таким образом, следующий фрагмент кода даст нам среднее значение без переполнения.

fn average_without_overflow(a: i32, b: i32) -> i32 {
    return (a & b) + ((a ^ b) >> 1);
}

Как работает этот трюк?

Сумма целых чисел может быть записана следующим образом:

sum = carries + sum without carries

Для расчета вышеуказанного мы можем сделать следующее:

a + b = ((a & b) << 1) + (a ^ b)                    [Eq.1]

Теперь деление на 2 равносильно сдвигу вправо на 1 бит.

Поэтому,

(a + b) / 2 = (a + b) >> 1                          [Eq.2]

Объединение [Eq.1] и [Eq.2]:

(a + b) / 2 = (a + b) >> 1 
            = ((( a & b ) << 1) + (a ^ b)) >> 1
            = (a & b) + ((a ^ b) >> 1)              [Eq.3]

Где >> — дистрибутив.

Пример:

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

Возьмем два INTa = 5 и b = 6 . Здесь b' обозначает двоичное представление.

a = b'101
b = b'110

Их целая сумма будет

a + b = 11 (decimal)
      = b'1011 (We can see it overflows)

Таким образом, у нас нет места, чтобы оставить здесь самый значимый бит. (Предположим, что наши числа имеют обратный порядок байтов).

Давайте применим [Eq.3]

a ^ b = b'101 ^ b'110
      = b'011
a & b = b'101 & b'110
      = b'100
(a ^ b) >> 1 = b'011 >> 1
             = b'001 (so dividing 1 by 2 is making the MSB 0)

Окончательно,

(a & b) + (a ^ b) >> 1 = b'100 + b'001
                       = b'101
                       = 5

Надеюсь, этот пример поможет получить четкую картину.

Код Rust можно найти здесь. https://gist.github.com/eNipu/6e8c3917865a4eb1e8cb34184d954d28

Это также будет работать для C/C++. Но не python, поскольку целые числа Python имеют произвольную точность. Мы можем проверить правильность этого трюка с помощью Python.