#include unsigned short popcount_0x5555(unsigned short n) { unsigned short x = n & 0x1111; x += (n & 0x4444)>> 2; x += x>> 4; x += x>> 8; return x & 0xf; } int mod3(unsigned short n) { int rv = 9 + popcount_0x5555(n) - popcount_0x5555(n>> 1); while (rv> 2) rv -= 3; return rv; } int main() { int ii; for (ii = 0; ii < 65536; ii++) { if (mod3(ii) != ii % 3) { printf("failure at %d: %d != %d\n", ii, mod3(ii), ii % 3); return 1; } } printf("success\n"); return 0; }