java - 高效的模 3 运算？

Question

<分区>

Answer 1

好吧，而不是通常的“测量它”，而是实际的答案 - 因为这些东西实际上是真正有趣的数学。尽管编译器可以并且可能也这样做(至少现代优化的 c++ 编译器，javac 肯定不会，而且我不知道 JVM 是否这样做) - 所以最好检查它是否已经完成了工作你。

但了解优化背后的理论仍然很有趣:我将使用汇编，因为我们需要乘法的高 32 位字。以下内容摘自 Warren 关于位运算的书:

n 是我们想要取模的输入整数:

li M, 0x55555556   ; load magical number (2^32 + 2) / 3
mulhs q, M, n      ; q = higher word of M * n; i.e. q = floor(M*n / 2^32)
shri t, n, 31      ; add 1 to q if it is negative
add q, q, t

这里 q 包含 n/3 的除数，因此我们只需像往常一样计算余数:r = n - q*3

数学是有趣的部分—— latex 在这里会很酷:

q = 楼层( (2^32+2)/3 * (n/2^32) ) = 楼层( n/3 + 2*n/(3*2^32) )

现在对于 n = 2^31-1(带符号的 32 位整数可能的最大 n)，误差项小于 1/3(并且非负)，这使得很容易证明结果确实是正确的。对于 n = -2^31，我们在上面进行了 1 的修正，如果你简化它，你会发现误差项总是大于 -1/3，这意味着它也适用于负数。

我将带有错误项边界的证明留给感兴趣的人——这并不难。