最优化的计算C模数的方法
我用C计算模数的成本最小化。假设我有一个数字x而n是将x除以的数字
当n == 65536（恰好是2 ^ 16）时：
mod = x％n（由GCC制作的11条assembly说明）或
mod = x＆0xffff等于mod = x＆65535（4个汇编指令）
因此，海湾合作委员会并未对此进行优化。
在我的情况下，n不是x ^（int），而是小于2 ^ 16的最大素数，即65521
正如我在n == 2 ^ 16中所展示的那样，逐位运算可以优化计算。 当n == 65521计算模数时，我可以执行哪些按位操作。
首先，确保在查看GCC正在生成的结论之前查看优化代码（并确保确实需要优化此特定表达式）。 最后 – 不要指望得出结论; 可能预期11指令序列比包括div指令的较短序列执行得更好。
此外，您不能得出结论，因为x mod 65536可以使用简单的位掩码计算，任何mod操作都可以通过这种方式实现。 考虑如何轻松除以十进制10而不是除以任意数。
完成所有这些后，您可以使用Henry Warren的Hacker’s Delight书中的一些“神奇数字”技术：
在网站上增加了一章 ，其中包含“两种计算除法余数而不计算商数的方法！”，您可能会发现它有些用处。 第一种技术仅适用于有限的除数，因此它不适用于您的特定实例。 我还没有真正阅读过在线章节，因此我不确切知道其他技术对您的适用程度。
如果x是无符号的，则x mod 65536仅等效于x和0xffff – 对于带符号x，它给出负数的错误结果。 对于无符号x，gcc确实将x % 65536优化为按位并使用65535（在我的测试中甚至在-O0上）。
因为65521不是2的幂，所以不能如此简单地计算x mod 65521。 gcc 4.3.2 on -O3使用x - (x / 65521) * 65521计算它; 使用整数乘以相关常数来完成常数的整数除法。
如果你不必完全减少你的整数模数65521，那么你可以使用65521接近2 ** 16的事实。 即如果x是一个unsigned int，你想减少，那么你可以做以下事情：
unsigned int low = x &0xffff; unsigned int hi = (x >> 16); x = low + 15 * hi;
这使用2 ** 16％65521 == 15.请注意，这不是完全减少。 即，从32位输入开始，您只能保证结果最多为20位，并且它当然与输入模65521一致。
此技巧可用于需要以相同常数模数减少许多操作的应用程序，并且中间结果不必是其残差类中的最小元素。
例如，一个应用程序是Adler-32的实现，它使用模数65521.这个散列函数以65521为模数执行大量操作。为了有效地实现它，只需经过仔细计算的加法次数后进行模块化约简。 如上所示的减少就足够了，只有散列的计算才需要完整的模运算。
如果除数的forms为2^n ，则按位运算仅适用。 在一般情况下，没有这样的按位操作。
如果你想要取模数的常量在编译时是已知的并且你有一个不错的编译器（例如gcc），通常最好让编译器发挥它的魔力。 只需声明模数const。
如果您在编译时不知道常量，但是您将采用相同数字的十亿模数，那么请使用此http://libdivide.com/
作为处理2的幂的方法，可以考虑这个（主要是C风格）：
. . #define THE_DIVISOR 0x8U; /* The modulo value (POWER OF 2). */ . . uint8 CheckIfModulo(const sint32 TheDividend) { uint8 RetVal = 1; /* TheDividend is not modulus THE_DIVISOR. */ if (0 == (TheDividend & (THE_DIVISOR - 1))) { /* code if modulo is satisfied */ RetVal = 0; /* TheDividend IS modulus THE_DIVISOR. */ } else { /* code if modulo is NOT satisfied */ } return RetVal; }
如果x是增加的指数，并且已知增量i小于n （例如，当在长度为n的圆形arrays上进行迭代时），则完全避免模数。 一个循环
x += i; if (x >= n) x -= n;
比…更快
x = (x + i) % n;
不幸的是，你在许多教科书中都找到了……
如果你真的需要一个表达式（例如，因为你在for语句中使用它），你可以使用丑陋但有效的
x = x + (x+i < n ? i : in)
idiv – 整数分部
idiv指令通过指定的操作数值划分64位整数EDX的内容：EAX（通过将EDX视为最重要的四个字节，EAX作为最不重要的四个字节构造）。 除法的商结果存储在EAX中，而余数存放在EDX中 。
来源： http ： //www.cs.virginia.edu/~evans/cs216/guides/x86.html
C中模数的最低成本实现
如何实施MOD如下：
要找到：y = X mod n
y = X-(X/n)*n
（假设X和n都是整数）
注意：对于assembly级别优化， 请按照Krystian的说明使用iDiv 。