我有一段代码，其中我计算 x % 25。x始终采用正值，但其动态范围很大。
我发现这个特定的代码片段计算 x % 25 需要大量的周期。我需要进行优化。
预先计算的查找表因可能需要的大内存大小而被排除。
作为第二种方法，我编写了下面的代码片段（C代码） -
mod(a, b)
{
int r = a;
while(r >= b)
{
r = r - b;
}
return r;
}
1.) 如何进一步优化这段代码，以获得更多的性能提升？
2.) 是否有完全不同的优化方法来实现 x % 25 (我知道这不是一个常见的操作，但仍然寻找聪明的输入，可能会帮助我)。
谢谢。
-AD
编辑：
我认为在C中使用本地模运算符％时，内部使用了除法操作（/），这在我使用的处理器上是昂贵的。（没有div指令）因此，尝试查看自定义实现是否可以击败使用％运算符的内在计算。
-AD
我建议阅读《Hacker's Delight》。它描述了用于常数除数的非常快速的余数算法。它们几乎肯定会击败通用算法。
更新：这里有一些示例代码......它可能可以重新设计以避免临时 long long。
unsigned mod25(unsigned n)
{
unsigned reciprocal = 1374389535; // 2^35 / 25
unsigned div25 = ((unsigned long long)n * reciprocal) >> 35;
return n - div25 * 25;
}
mull和一个shrl指令（由于寄存器中的值的位置，移位只会是3而不是35）。 - Christophint mod(int a, int b) {
int s = b;
while (s <= a) {
s <<= 1;
}
int r = a;
while (r >= b) {
s >>= 1;
if (s <= r) {
r -= s;
}
}
return r;
}
这个方法会从a中减去b的2的倍数，直到找到结果。
编辑：添加if条件以使其正常工作。
例如，如果要计算100 % 7，它首先计算出7 * 2 * 2 * 2 * 2 = 112。然后它将112 (s)除以2并从100 (r)中减去（当s <= r时），并不断重复此过程直到找到模数为止。因此，
s = 112 / 2 = 56, r = 100 - 56 = 44
s = 56 / 2 = 28, r = 44 - 28 = 16
s = 28 / 2 = 14, r = 16 - 14 = 2
以下是我的解决方案：
int mod25(int x){
/* 25 * (all powers of 2 <= INT_MAX), descending */
if (x >= 1677721600) x -= 1677721600;
if (x >= 838860800) x -= 838860800;
if (x >= 419430400) x -= 419430400;
if (x >= 209715200) x -= 209715200;
if (x >= 104857600) x -= 104857600;
if (x >= 52428800) x -= 52428800;
if (x >= 26214400) x -= 26214400;
if (x >= 13107200) x -= 13107200;
if (x >= 6553600) x -= 6553600;
if (x >= 3276800) x -= 3276800;
if (x >= 1638400) x -= 1638400;
if (x >= 819200) x -= 819200;
if (x >= 409600) x -= 409600;
if (x >= 204800) x -= 204800;
if (x >= 102400) x -= 102400;
if (x >= 51200) x -= 51200;
if (x >= 25600) x -= 25600;
if (x >= 12800) x -= 12800;
if (x >= 6400) x -= 6400;
if (x >= 3200) x -= 3200;
if (x >= 1600) x -= 1600;
if (x >= 800) x -= 800;
if (x >= 400) x -= 400;
if (x >= 200) x -= 200;
if (x >= 100) x -= 100;
if (x >= 50) x -= 50;
if (x >= 25) x -= 25;
return x;
}
这段代码没有使用除法或乘法，只有27次比较和最多27次减法。
虽然有点难以让自己相信这个方法是有效的，但确实是有效的（至少对于非负的x值来说）。
上面的代码实际上是下面代码的展开：
int mod25(int x){
int divisor;
for(int divisor = 1677721600; divisor >= 25; divisor >>= 1) {
if (x >= divisor) x -= divisor;
}
return x;
}
哦，我的神啊。我简直无法相信这些答案。
首先，即使是Pax的版本，重复减法也永远不会是最优解。考虑以下情况：
20 % 25
65535 % 25
这样做会非常缓慢，需要600多次迭代。平均每16位数字需要300次迭代。至于32位数字，最好别去碰它。
最快的方法是使用长除法，可以参考Niki的答案。
不过，编译器生成的代码应该也是这个样子的，至少我们希望编译器会生成这样的代码。如果你使用的是一种小众处理器的编译器，最好还是核实一下。
加速的最佳方式是避免进行模运算。你为什么需要求模？你能否重新设计代码/算法来避免模运算，或者将模运算变得微不足道。
int mod25(int x)
{
while((x = (x & 31) + 7 * (x >> 5)) >= 25)
x -= 25;
return x;
}
它使用 x % 32 + 7 * (x/32) 来近似计算 x % 25。该值会超出 25 的倍数，这允许递归。
性能似乎是足够的：对于值 x = 2147483647（也称为INT_MAX），需要 11 次迭代。
如果你想要用一个常数来求模，那么你可以通过倒数乘法轻松实现。 这篇文章 展示了如何以这种方式除以常数，并在最后展示了如何得到余数。
您的循环存在问题，因为它是O(n)的 - 对于较大的r值，速度会非常慢。我建议使用以下代码：
for (int s = MAX_SHIFT; s>=0; s--)
if (r > (b<<s)) r -= (b<<s);
但我怀疑您的编译器并没有做比这更昂贵的事情。
如果您的C编译器的目标CPU没有除法指令，您可以按照以下方式修改代码：
mod(a, b) {
int s = b + b + b + b;
int r = a;
while(r >= s) {
r -= s;
}
while(r >= b) {
r -= b;
}
return r;
}
这种方法是将数值按四个一组相减，直到最后一个，然后切换为每次只减去一个。
这样做可以使您的代码运行速度约快四倍（假设4*b不超出整数范围）。您甚至可以在4*b之前插入更多循环（比如8*b），以获得更快的速度。
除此之外，手写汇编可能会有所帮助，但我认为您会发现上述代码已经有了相当大的提升，无需手写汇编。
如果您对使用模运算的方式有更多细节了解，可以针对特定情况进行优化。例如，如果您只想知道16位整数的模25，下面的代码比具有变量分母的简单循环要快得多。
int mod25 (int a) { // a has maximum value of 2^15-1 = 32767
while (a >= 15625) a-= 15625; // at most 2 times.
while (a >= 625) a-= 625; // at most 24 times.
while (a >= 25) a-= 25; // at most 24 times.
return a;
}
%操作符之间出现明显差异之前，你必须进行1000万次迭代（2秒 vs. 0秒）。在那之前，它们都是0秒，尽管这是在一台快速的机器上运行的（对于mod25更好），并且使用了div指令（对于%操作符更好），因此你需要在自己的硬件上进行基准测试。int mod (int n, int d) {
/* dx is the adjusted denom, don't let it overflow though. */
int dx = d;
while (((dx << 1) >>1) == dx)
dx <<= 1;
/* This loop processes the dx values until they get too small. */
while (dx >= d) {
/* This loop subtracts the large dx value. */
while (n >= dx)
n -= dx;
dx >>= 1;
}
return n;
}
实际上，这个更通用的解决方案的性能与上面优化版本的mod25相当。