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的速度快?如果是这样,那可能不是很多。