Давайте вычислим среднее значение двух целых чисел и вернем среднее значение как 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.