performance - 快速模 3 或除法算法？

Question

有没有一个快速的算法，类似2的幂，可以和3一起使用，即n%3。 也许是利用了这样一个事实，即如果数字之和可以被三整除，那么这个数字也可以被整除。

这引出了下一个问题。在数字中添加数字的快速方法是什么？ IE。 37 -> 3 +7 -> 10 我正在寻找没有条件的东西，因为它们往往会抑制矢量化

谢谢

Answer 1

4 % 3 == 1，所以 (4^k * a + b) % 3 == (a + b) % 3。您可以使用这个事实来计算 32 位 x 的 x%3:

x = (x >> 16) + (x & 0xffff);
x = (x >> 10) + (x & 0x3ff);
x = (x >> 6) + (x & 0x3f);
x = (x >> 4) + (x & 0xf);
x = (x >> 2) + (x & 0x3);
x = (x >> 2) + (x & 0x3);
x = (x >> 2) + (x & 0x3);
if (x == 3) x = 0;

(未经测试 - 您可能需要再减少一些。)这是否比您的硬件快 x%3？如果是，则可能相差不大。