I am looking for a bit-wise test equivalent to `(num%2) == 0 || (num%3) == 0`

.

I can replace `num%2`

with `num&1`

, but I’m still stuck with `num%3`

and with the logical-or.

This expression is also equivalent to `(num%2)*(num%3) == 0`

, but I’m not sure how that helps.

## Answer

Yes, though it’s not very pretty, you can do something analogous to the old “sum all the decimal digits until you have only one left” trick to test if a number is divisible by 9, except in binary and with divisibility by 3. You can use the same principle for other numbers as well, but many combinations of base/divisor introduce annoying scaling factors so you’re not just summing digits anymore.

Anyway, 16^{n}-1 is divisible by 3, so you can use radix 16, that is, sum the nibbles. Then you’re left with one nibble (well, 5 bits really), and you can just look that up. So for example in C# (slightly tested) edit: brute-force tested, definitely works

static bool IsMultipleOf3(uint x) { const uint lookuptable = 0x49249249; uint t = (x & 0x0F0F0F0F) + ((x & 0xF0F0F0F0) >> 4); t = (t & 0x00FF00FF) + ((t & 0xFF00FF00) >> 8); t = (t & 0x000000FF) + ((t & 0x00FF0000) >> 16); t = (t & 0xF) + ((t & 0xF0) >> 4); return ((lookuptable >> (int)t) & 1) != 0; }

The trick from my comment, `x * 0xaaaaaaab <= 0x55555555`

, works through a modular multiplicative inverse trick. 0xaaaaaaab * 3 = 1 mod 2^{32}, which means that `0xaaaaaaab * x = x / 3`

if and only if`x % 3 = 0`

. “if” because `0xaaaaaaab * 3 * y = y`

(because `1 * y = y`

), so if `x`

is of the form`3 * y`

then it will map back to `y`

. “only if” because no two inputs are mapped to the same output, so everything not divisible by 3 will map to something higher than the highest thing you can get by dividing anything by 3 (which is `0xFFFFFFFF / 3 = 0x55555555`

).

You can read more about this (including the more general form, which includes a rotation) in Division by Invariant Integers using Multiplication (T. Granlund and P. L. Montgomery).

You compiler may not know this trick. For example this:

uint32_t foo(uint32_t x) { return x % 3 == 0; }

Becomes, on Clang 3.4.1 for x64,

movl %edi, %eax movl $2863311531, %ecx # imm = 0xAAAAAAAB imulq %rax, %rcx shrq $33, %rcx leal (%rcx,%rcx,2), %eax cmpl %eax, %edi sete %al movzbl %al, %eax ret

G++ 4.8:

mov eax, edi mov edx, -1431655765 mul edx shr edx lea eax, [rdx+rdx*2] cmp edi, eax sete al movzx eax, al ret

What it should be:

imul eax, edi, 0xaaaaaaab cmp eax, 0x55555555 setbe al movzx eax, al ret