有效的Modulo 3操作？

Question

可能重复：

Fast modulo 3 or division algorithm?

每个人都知道，模块化算法可能是性能的一个巨大缺陷。有谁知道x%3操作的好替代方案吗？我知道它存在于x%2，但我确实需要一个模块3，因为我想在一个for循环中在三个缓冲区之间交替使用。

谢谢!

Answer 1

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

但是，了解优化背后的理论仍然很有趣:我将使用程序集，因为我们需要更高的32位乘法词。以下是沃伦的“比特旋转”一书：

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

数学是有趣的部分--乳胶在这里会很酷：

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，这意味着它也适用于负数。

我把错误项的证明留给感兴趣的人--这并不难。

Answer 2

如果它是一个直线的循环，不需要计算一个模。持有每3步重置一次的第二个int var。

int i, bn = 0;

for(i=0; i<whatever; i++) {
  ...
  if(++bn == 3) bn = 0;
}

这不是一个过早的优化，而是在避免不必要的计算。

编辑: OP中提到，他使用一个循环在缓冲区之间切换，所以我的解决方案看起来非常合适。至于否决投票，如果是错误的话，没问题。

Answer 3

如果在编译时已知3，那么编译器将生成“技巧”，以尽可能高效地完成它。在运行时，当除数未知时，模块所需时间要长得多。