简化表达式 k/m%n

Question

简单问题，是否有可能简化（或替换除法或取模运算为更少的操作）？

(k/m)%n

变量为整数，操作符为C语言风格的除法和取模运算符。

让我稍微改一下问题，除了变量是base2的情况，什么条件下（例如某些变量可能是常数），表达式可以简化（或者部分地使用base2操作重新表述）以消除除法或取模？

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

谢谢

- Anycorn

---

只有当您对值具有一些额外的先验知识时，例如如果m是一个常数或n是2的幂次方时，才能这样做。 - Paul R

@Paul 我更新了问题以考虑到你的评论。 - Anycorn

整数是常规的机器字（例如32位），还是任意精度的？ - Gabe

@Gabe 我猜无所谓，哪个更容易推导就用哪个。 - Anycorn

不是真正的答案，因为你可能知道：(k/m)%n == ((k%n)/(m%n))%n更难了？但是除法是用较小的数字进行的。 - Fabio Filippi

Answer 1

明显的优化：

1. m == 1：答案将是 k % m。
2. n == 1：答案总是 0。
3. m 是2的幂：例如，如果 m 是4，则可以使用 (k >> 2) % n；
4. n 是2的幂：表达式变为 (k / m) & (n - 1)；

检查 #1 和 #2 很容易。

通过使用以下方法检查是否为2的幂：

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

- Peter Alexander

---

请注意，您的isPowerOfTwo函数仅适用于x> 0的值。 - Paul R

没错，但是在这种情况下，如果有人除以0或取模数为0，那么他们会遇到更大的问题 :) - Peter Alexander

只是一个小问题：isPowerOfTwo函数的返回类型应该是无符号整数。 - I. J. Kennedy

Answer 2

对于小常数分母的除法，您可以使用类似以下的内容。

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

黑客的乐趣一书中有关于整数除法的章节。

针对2的幂次方进行简单的模和除法。

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

- drawnonward

Answer 3

对于任意精度整数，我建议查看http://documents.epfl.ch/users/k/ka/kaihara/www/papers/ModMulDiv_Binary.pdf。该文献提供了一种硬件方法，但它提供了您可以适应的伪代码。

- Gabe

Answer 4

补充Peter Alexander的答案：

0) 当然，m != 0 && n != 0 是前提条件...

1) k < m：答案总是0

2) k == m：答案总是1（除非n也为1，参见5.）

3) k / m < n：答案为k / m

4) k < (m * n)：答案总是k / m。这个特定条件不利于优化，因为m*n不会被重复使用，而且它不应该比模运算快多少，除非m和/或n是2的幂，在这种情况下，你仍然最好使用7.和/或8.

供参考，添加Peter Alexander的：

5) m == 1：答案将只是k % n。

6) n == 1：答案总是0。

7) m是2的幂：例如，如果m为4，则可以使用(k >> 2) % n;

8) n是2的幂：表达式变为(k / m) & (n - 1);

- njsf

Answer 5

我想这取决于情况。

正确的算术右移会使您除以2，通过一些附加算术运算，您可以将其转换为除以任何数字。

同样，我认为您可以使用模运算符做同样的事情。

实际上，除非您的处理器缺少必要的硬件，否则我认为您不会获得任何好处。

编辑 实际上，仔细考虑一下，对于负数来说，有符号移位不起作用，因为它不能被2整除。

如果我没记错的话，在C标准中，算术右移的行为对于负数是未定义的（它谈论了2的幂），因此与编译器相关。

如果我们只考虑数论的逻辑，那就是另一回事了。让我想一想。

- ChrisBD

---

这是关于编程的内容，需要将其从英语翻译成中文。只需返回已翻译的文本即可：这并不是紧急需求，只是想了解可能性。 - Anycorn