时间戳

首页 > 解决方案 > 通过乘法和移位舍入整数除法

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

问题描述

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

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

标签： bit-manipulationroundingdivision

解决方案

我想出了：

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

推荐阅读