Округление целочисленного деления на умножение и сдвиг - PullRequest
Новая
       28

Округление целочисленного деления на умножение и сдвиг

0 голосов
/ 04 сентября 2018

Я узнал об этом трюке на днях, проверив машинный код, сгенерированный gcc. Деление целого числа a на константу b можно оптимизировать следующим образом: 

x = a / b
x = a * (1 / b)
x = (a * (((1 << n) / b) + 1)) >> n

Обратная величина может быть оценена во время компиляции, что приводит к операции умножения и сдвига, которая более эффективна, чем деление. 

c = ((1 << n) / b) + 1
x = (a * c) >> n

Теперь это имеет тот же эффект, что и простое целочисленное деление, оно усекает результат (округление до нуля). Можно ли изменить этот алгоритм для округления до ближайшего значения вместо этого?

1 Ответ

0 голосов
/ 04 сентября 2018

Я придумал: 

c = (1 << n) / b
d = a * c
x = ((d >> (n - 1)) & 1) + (d >> n)

Трюк, но мне интересно, есть ли более эффективные методы.

edit: я задал тот же вопрос на reddit и получил лучший ответ: https://www.reddit.com/r/AskProgramming/comments/9cx9dl/rounding_integer_division_by_multiplyandshift/

c = ((1 << n) + b - 1) / b;
x = (((a * c) >> (n - 1)) + 1) >> 1

Еще один сдвиг можно удалить, определив другую константу: 

e = 1 << (n - 1)
x = (a * c + e) >> 1
...