c - 在 C 中计算模数的最优化方法

Question

我已将 C 中计算模数的成本降至最低。假设我有一个数字 x，n 是除以 x 的数字

当 n == 65536(恰好是 2^16)时:

mod = x % n(GCC 生成的 11 条汇编指令)或者
mod = x & 0xffff 等于 mod = x & 65535(4 条汇编指令)

因此，GCC 并未将其优化到这种程度。

在我的例子中，n 不是 x^(int)，而是小于 2^16 的最大素数，即 65521

正如我在 n == 2^16 中展示的那样，按位运算可以优化计算。当 n == 65521 计算模数时，我可以执行哪些位操作。

Answer 1

首先，在得出关于 GCC 正在生成什么的结论之前，请确保您正在查看优化的代码(并确保这个特定的表达式确实需要优化)。最后——不要指望指令来得出你的结论；可能期望 11 条指令序列比包含 div 指令的较短序列执行得更好。

此外，您不能断定因为 x mod 65536 可以用简单的位掩码计算，所以任何模运算都可以通过这种方式实现。想一想除以十进制数与除以任意数字相比有多么容易。

完成所有这些后，您也许可以使用 Henry Warren 的 Hacker's Delight 书中的一些“神奇数字”技术:

• Archive of http://www.hackersdelight.org/
• Archive of http://www.hackersdelight.org/magic.htm

有一个 added chapter on the website其中包含“计算除法余数而不计算商的两种方法!”，您可能会发现它有一些用处。第一种技术仅适用于一组有限的除数，因此它不适用于您的特定实例。我还没有真正阅读在线章节，所以我不知道其他技术对您的适用性如何。