通过乘法和移位舍入整数除法

Question

前几天我通过检查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

现在这与普通整数除法具有相同的效果，它会截断结果（向零舍入）。是否可以修改此算法以舍入最接近的值？

Answer 1

我提出了：

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

有诀窍，但我想知道是否有更有效的方法。

编辑：我在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