有没有办法在没有模数/除法运算符的情况下编写“mod 31”？
如果操作数是2的幂，则可以在没有模数运算符或除法的情况下容易地获得数字的模数。在这种情况下，下面的公式成立： x % y = (x & (y − 1)) 。 在许多架构中，这通常很有效。 mod 31也可以这样做吗？
int mod31(int a){ return a % 31; };
以下是解决此问题的两种方法。 第一个使用普通的bit-twiddling技术，如果仔细优化可以击败硬件分区。 另一个用乘法替换除数，类似于gcc执行的优化，并且是最快的。 最重要的是， 如果第二个参数是常量 ， 那么试图避开%运算符并没有多大意义，因为gcc已经覆盖了它。 （也可能是其他编译器。）
以下函数基于以下事实： x与x的基数为32的数字之和相同（mod 31）。 这是真的，因为32是1 mod 31 ，因此32任何幂是1 mod 31 。 因此，基数为32的数字中的每个“数字”位置将数字* 1贡献给mod 31总和。 并且很容易得到base-32表示：我们一次只取五位。
（就像这个答案中的其他函数一样，它只适用于非负x ）。
unsigned mod31(unsigned x) { unsigned tmp; for (tmp = 0; x; x >>= 5) { tmp += x & 31; } // Here we assume that there are at most 160 bits in x tmp = (tmp >> 5) + (tmp & 31); return tmp >= 31 ? tmp - 31 : tmp; }
对于特定的整数大小，您可以展开循环并且很可能击败除法。 （并且请参阅@ chux的答案 ，将循环转换为O(log bits)操作而不是O(bits)更难以击败gcc ，这避免了当被除数是编译时已知的常数时的除法。
在使用无符号32位整数的非常快速的基准测试中，天真的展开循环花费了19秒，基于@ chux的答案的版本仅用了13秒，但gcc的x%31花费了9.7秒。 强制gcc使用硬件除法（通过使除法非常数）花费23.4秒，并且如上所示的代码花费25.6秒。 这些数字应该用几粒盐。 时间用于计算i%31在笔记本电脑上使用-O3 -march=native所有可能值的i%31 。
gcc通过用基本上64位乘法乘以常数的倒数后跟右移来避免32位除以常数。 （实际的算法做了一些工作以避免溢出。）该程序在20多年前在gcc v2.6 ，描述该算法的论文可在gmp站点上获得 。 （GMP也使用这个技巧。）
这是一个简化版本：假设我们想为某些无符号的32位整数n计算n // 31 （使用pythonic //来表示截断的整数除法）。 我们使用“魔法常数” m = 2 32 // 31 ，即138547332 。 现在很明显，任何n ：
m * n <= 2 32 * n/31 < m * n + n ⇒ m * n // 2 32 <= n//31 <= (m * n + n) // 2 32
（这里我们利用这样a < b事实：如果a < b然后是floor(a) <= floor(b) 。）
此外，由于n < 2 32 ， m * n // 2 32和(m * n + n) // 2 32是相同的整数或两个连续的整数。 因此，这两者中的一个（或两个）是n//31的实际值。
现在，我们真的想要计算n%31 。 所以我们需要将（假定的）商乘以31，然后从n减去它。 如果我们使用两个可能的商中较小的一个，可能会发现计算的模数值太大，但它只能太大31。
或者，把它放在代码中：
static unsigned long long magic = 138547332; unsigned mod31g(unsigned x) { unsigned q = (x * magic) >> 32; // To multiply by 31, we multiply by 32 and subtract unsigned mod = x - ((q << 5) - q); return mod < 31 ? mod : mod - 31; }
gcc使用的实际算法通过使用基于乘以2 37 //31 + 1的稍微更精确的计算来避免最后的测试。 这总是产生正确的商，但代价是一些额外的移位并增加以避免整数溢出。 事实certificate，上面的版本稍微快一点 - 在与上面相同的基准测试中，只用了6.3秒。
其他基准function，完整性：
天真的展开循环
unsigned mod31b(unsigned x) { unsigned tmp = x & 31; x >>= 5; tmp += x & 31; x >>= 5; tmp += x & 31; x >>= 5; tmp += x & 31; x >>= 5; tmp += x & 31; x >>= 5; tmp += x & 31; x >>= 5; tmp += x & 31; tmp = (tmp >> 5) + (tmp & 31); return tmp >= 31 ? tmp - 31 : tmp; }
@ chux的改进，略微优化
static const unsigned mask1 = (31U << 0) | (31U << 10) | (31U << 20) | (31U << 30); static const unsigned mask2 = (31U << 5) | (31U << 15) | (31U << 25); unsigned mod31c(unsigned x) { x = (x & mask1) + ((x & mask2) >> 5); x += x >> 20; x += x >> 10; x = (x & 31) + ((x >> 5) & 31); return x >= 31 ? x - 31: x; }
[Edit2]下面是性能说明
只有1 if条件的尝试。
这种方法是O（log2（sizeof unsigned））。 如果代码使用uint64_t运行时间将增加1组ands / shifting / add而不是两倍的循环方法。
unsigned mod31(uint32_t x) { #define m31 (31lu) #define m3131 ((m31 << 5) | m31) #define m31313131 ((m3131 << 10) | m3131) static const uint32_t mask1 = (m31 << 0) | (m31 << 10) | (m31 << 20) | (m31 << 30); static const uint32_t mask2 = (m31 << 5) | (m31 << 15) | (m31 << 25); uint32_t a = x & mask1; uint32_t b = x & mask2; x = a + (b >> 5); // x = xx 0000x xxxxx 0000x xxxxx 0000x xxxxx a = x & m31313131; b = x & (m31313131 << 20); x = a + (b >> 20); // x = 00 00000 00000 000xx xxxxx 000xx xxxxx a = x & m3131; b = x & (m3131 << 10); x = a + (b >> 10); // x = 00 00000 00000 00000 00000 00xxx xxxxx a = x & m31; b = x & (m31 << 5); x = a + (b >> 5); // x = 00 00000 00000 00000 00000 0000x xxxxx return x >= 31 ? x-31 : x; }
[编辑]
第一加法方法并行地将各个7组五个比特相加。 随后的加法使7组进入4，然后是2，然后是1.最后的7位和然后继续将其上半部分（2位）加到其下半部分（5位）。 然后代码使用一个测试来执行最终的“mod”。
此方法将更宽的unsigned扩展至至少uint165_t log2（31 + 1）*（31 + 2）。 通过它，需要更多的代码。
请参阅@rici以获得一些很好的优化。 仍然建议使用uint32_t与unsigned和31UL的移位，如31U << 15因为unsigned 31U可能只有16位长。 （2014年在嵌入式世界中流行的16位int ）。
[EDIT2]
除了让编译器使用其优化器之外，另外两种技术可以提高性能。 这些是更小的客厅技巧，取得了适度的改善。 请记住YMMV ，这是一个32位unsigned 。
使用查表最后一个modulo提高了10-20％。 使用unsigned t表而不是unsigned char t有所帮助。 原来，表长度，首先预计需要2 * 31，只需要31 + 5。
使用局部变量而不是总是调用函数参数令人惊讶地帮助。 可能是我的gcc编译器的弱点。
发现非分支解决方案（未显示）替换x >= 31 ? x-31 : x x >= 31 ? x-31 : x 。 但是他们的编码复杂性更高，性能更慢。
总而言之，这是一项有趣的运动。
unsigned mod31quik(unsigned xx) { #define mask (31u | (31u << 10) | (31u << 20) | (31u << 30)) unsigned x = (xx & mask) + ((xx >> 5) & mask); x += x >> 20; x += x >> 10; x = (x & 31u) + ((x >> 5) & 31u); static const unsigned char t[31 * 2 /* 36 */] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 0, 1, 2, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; return t[x]; }
如果你想得到分母模数除以分母d使得d = (1 << e) - 1 ，其中e是一个指数，你可以使用1/d的二进制展开是带位的重复分数这一事实设置每个e位数。 例如，对于e = 5 ， d = 31 ，并且1/d = 0.0000100001...
与rici的答案类似，该算法有效地计算了a的基数 (1 << e)数字的总和：
uint16_t mod31(uint16_t a) { uint16_t b; for (b = a; a > 31; a = b) for (b = 0; a != 0; a >>= 5) b += a & 31; return b == 31 ? 0 : b; }
你可以展开这个循环，因为分母和分子中的位数都是常量，但让编译器这样做可能更好。 当然，您可以将5更改为输入参数，将31更改为由此计算的变量。
您可以使用连续的加法/减法。 没有其他技巧，因为31是素数，看看数字N的模数是什么模型31你必须除以并找到余数。
int mode(int number, int modulus) { int result = number; if (number >= 0) { while(result > modulus) { result = result - modulus;} } else { while (result < 0) { result = result + modulus;) } }
int mod31(int a){ while(a >= 31) { a -= 31; } return a; };
如果a > 0 ，它可以工作，但我怀疑它会比% operator更快。