# Is there a bit-wise trick for checking the divisibility of a number by 2 or 3?

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, 16n-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 232, 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
```