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

Leave a Reply

Your email address will not be published. Required fields are marked *