简化表达式k/m%n

Question

简单的问题是,是否可以通过更便宜的操作来简化(或替换除法或模数)

(k/m)%n

其中变量是整数,运算符是C样式除法和模运算符.

让我稍微重新解释一下问题,除了变量是base2的情况,在什么条件下(例如某些变量可能是常量)可以简化表达式(或者使用base2操作部分重新表达)来删除除法或模数？

这是我学习数论的方法,特别是base2技巧,而不是练习性能优化

谢谢

Answer 1

对于具有小常数分母的除法，您可以使用类似的方法。

k/m=k*(1/m)
x=(1<<16)/m
k/m=(k*x)>>16

根据输入的不同，答案可能不准确。

对于小奇常数分母的除法，可以使用乘法逆元。以下常量适用于 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有一个关于整数除法的章节。

简单模数和二的幂除法。

x%m == x&(m-1)
x/m == x>>log2(m) // assumes log2(m) is known, not calculated