在 32 位整数数学中，加法和乘法的基本数学运算是隐式计算的，模 2^32，这意味着您的结果将是加法或乘法的最低位。
如果你想用不同的模数计算结果，你当然可以使用不同语言的任意数量的 BigInt 类。对于 a,b,c < 2^32 的值，您可以计算 64 位长整数的中间值，并使用内置的 % 运算符来减少到正确的答案
但是有人告诉我，当 C 的形式为 (2^N)-1 或 (2^N)+1，不使用 64 位数学或一个 BigInt 库，并且非常有效，比任意模计算更有效，并且还可以正确计算如果包含中间乘法，通常会溢出 32 位 int 的情况。
不幸的是，尽管听说这种特殊情况有快速评估方法，但我实际上并没有找到该方法的描述。“那不是在 Knuth 吗？” “这不是维基百科的某个地方吗？” 是我听到的喃喃自语。
这显然是随机数生成器中的一种常用技术，因为 2147483647 是一个等于 2^31 -1 的素数，所以它对 a*b mod 2147483647 进行乘法运算。
所以我会问专家。这个我找不到任何讨论的聪明的特殊情况乘法与mod方法是什么？
我认为诀窍如下（我打算以 10 为底，因为它更容易，但原则应该成立）
假设你在乘法a*b mod 10000-1，并且
a = 1234 = 12 * 100 + 34
b = 5432 = 54 * 100 + 32
现在a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32
12 * 54 * 10000 = 648 * 10000
34 * 54 * 100 = 1836 * 100
12 * 32 * 100 = 384 * 100
34 * 32 = 1088
从x * 10000 ≡ x (mod 10000-1)[1] 开始，第一项和最后一项变为 648+1088。第二个和第三个术语是“技巧”的来源。请注意：
1836 = 18 * 100 + 36
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1).
这本质上是一个循环移位。给出 648 + 3618 + 8403 + 1088 的结果。还要注意，在所有情况下，相乘的数字都 < 10000（因为 a < 100 和 b < 100），所以如果你只能将多个 2 位数字放在一起，这是可以计算的, 并添加它们。
在二进制中，它会以类似的方式工作。
以 a 和 b 开头，都是 32 位。假设您想将它们相乘 mod 2^31 - 1，但您只有一个 16 位乘法器（给出 32 位）。该算法将是这样的：
a = 0x12345678
b = 0xfedbca98
accumulator = 0
for (x = 0; x < 32; x += 16)
for (y = 0; y < 32; y += 16)
// do the multiplication, 16-bit * 16-bit = 32-bit
temp = ((a >> x) & 0xFFFF) * ((b >> y) & 0xFFFF)
// add the bits to the accumulator, shifting over the right amount
total_bits_shifted = x + y
for (bits = 0; bits < total_bits_shifted + 32; bits += 31)
accumulator += (temp >> (bits - total_bits_shifted)) & 0x7FFFFFFF
// do modulus if it overflows
if (accumulator > 0x7FFFFFFFF)
accumulator = (accumulator >> 31) + (accumulator & 0x7FFFFFFF);
为时已晚，因此其中的累加器部分可能无法正常工作。我认为原则上它是正确的。有人可以随意编辑它以使其正确。
展开，这也相当快，我猜这也是 PRNG 使用的。
[1]: x*10000 ≡ x*(9999+1) ≡ 9999*x + x ≡ x (mod 9999)
假设您可以将 a*b 计算为p*2^N+q。这可能需要 64 位计算，或者您可以将 a 和 b 拆分为 16 位部分并在 32 位上进行计算。
那么a*b mod 2^N-1 = p+q mod 2^N-1自2^N mod 2^N-1 = 1.
并且a*b mod 2^N+1 = -p+q mod 2^N+1由于2^N mod 2^N+1 = -1.
在这两种情况下，都没有除以2^N-1or 2^N+1。
快速搜索一下：http ://home.pipeline.com/~hbaker1/AB-mod-N.pdf 。不幸的是，我现在已经太迟了，无法理解这一点，只写简化公式，但它可能在那篇论文中的某个地方。
您正在寻找的身份是x mod N = (x mod 2^q)- c*floor(x/2^q)，因为N = 2^q + c并且 c 是任何整数（但通常是±1）。
您可能需要阅读Richard Crandall 和 Carl Pomerance的“素数：计算视角”中的第 9.2.3 节：“特殊形式的模”。除了理论，它还包含实现上述关系的算法的伪代码。
我找到了一个关于这个主题的相当广泛的页面，不仅讨论了算法，还讨论了问题和解决方案的具体历史以及人们使用解决方案的方式。