简化表达式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

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

对于具有小的奇数常数分母的除法，可以使用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

Answer 2

对于任意精度的整数，我建议使用http://documents.epfl.ch/users/k/ka/kaihara/www/papers/ModMulDiv_Binary.pdf

它提供了一种硬件方法，但它提供了您可以适应的伪代码。

Answer 3

明显的优化：

表达式1:答案将只是表达式1:答案总是表达式是2的幂:例如，如果m是4，你可以使用(k >> 2) % n;

• n is a k % m.

• n 2：

1. == ==

检查#1和#2是微不足道的。

使用以下命令检查2的幂：

void isPowerOfTwo(unsigned int x)
{
    return x & (x - 1) == 0;
}