快速模3或除法算法？

Question

有一个快速的算法,类似于2的幂,可以使用3,即n%3.也许是使用这样一个事实:如果数字的总和可以被3整除,那么这个数字也是可以整除的.

这导致了下一个问题.在数字中添加数字的快捷方式是什么？即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快吗？如果是的话,可能不是很多.