计算 2^2？% uint64_t

Question

如何有效计算 2\xc2\xb9\xc2\xb2\xe2\x81\xb8 % n，其中 n 为uint64_t（且非零）？

\n

如果我能够像_udiv128MSVC 的内在那样缩小范围，我可以这样做：

\n

uint64_t remainder;\n_udiv128(1, 0, n, &remainder);\n_udiv128(remainder, 0, n, &remainder);\n

\n

但这是两条慢指令，更不用说像 ARM 这样的 CPU 没有缩小除法。有没有更好的办法？

\n

相关：如何在 C 中计算 2\xe2\x81\xb6\xe2\x81\xb4/n？

\n

Answer 1

通过一个简单的技巧，可以将缩小划分的数量减少到 1：

uint64_t remainder;
_udiv128(-n % n, 0, n, &remainder);

-n % n仍然需要 64 位除法，但是除数的上半部分为零的除法往往会更有效（当然比“完整”更有效libdivide_128_div_64_to_64，使用其慢速路径，这会花费两个 64 位除法加上一堆额外的东西）。不过，一些处理器不太关心股息的非零上半部分。

这个技巧之所以有效，是因为 2 ⁶⁴肯定大于n，所以我们可以n从中减去一次，然后我们得到 2 ⁶⁴ -n ，它等于-n计算的模 2 ⁶⁴（ uint64_t 上的算术是模 2 ⁶⁴）。我们不能只放入-n被除数的高位部分，因为这样商会变得太大并且除法会出错，而是需要使用专用的 128 位乘 64 位余数运算（与除法相反，除法也会产生余数作为副产品）可以支持这一点。确实如此-n % n。

内部函数_udiv128可以替换为libdivide_128_div_64_to_64支持其他平台的调用。

对我来说似乎有道理（考虑到本案的特殊性）还有更多的技巧，但我不知道它们，也找不到它们。我遇到的一个常见建议是使用平方求幂，但如果从字面上看，首先需要 6 个步骤才能达到-n % n（我们也可以从这个开始，然后只做一个平方），并且不能解决最大的问题问题：_udiv128没有 . 该怎么办_udiv128？对我来说，平方-n % n然后减少 modn似乎并不比乘以-n % n2 ⁶⁴然后减少 mod更好n，它只是花费了额外的乘法（具有 128 位输出），然后给我们留下了一个同样烦人的问题。