简单的问题,是否有可能简化(或用更便宜的操作代替除法或取模)
(k/m)%n
其中变量是整数,运算符是 C 风格的除法运算符和模运算符。
让我稍微改一下问题,除了变量是 base2 的情况外,在什么条件下(例如,某些变量可能是常量)可以简化表达式(或使用 base2 操作部分改写)以删除除法或取模?
这是我学习数论的方式,尤其是 base2 技巧,而不是练习性能优化
谢谢
最佳答案
对于小常数分母的除法,你可以使用这样的东西。
k/m=k*(1/m)
x=(1<<16)/m
k/m=(k*x)>>16
答案可能不准确,具体取决于输入。
对于小奇常数分母的除法,你可以使用 multiplicative inverse .以下常量适用于 32 位除法。
3 2863311531 11 3123612579
5 3435973837 13 3303820997
7 3067833783 15 4008636143
9 954437177 17 4042322161
x/11 == x*3123612579 % 2^32
% 2^32
在 32 位整数上当然是免费的。要将此应用于偶数,请分解出两个并在以后应用它们。
x/44 == (x*3123612579 % 2^32) >> 2
Hackers Delight有一章是关于整数除法的。
2 的幂的简单模数和除法。
x%m == x&(m-1)
x/m == x>>log2(m) // assumes log2(m) is known, not calculated
关于algorithm - 简化表达式 k/m%n,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3011866/