java - 是否有用于检查数字是否被 2 或 3 整除的位技巧？

Question

我正在寻找等同于 (num%2) == 0 || 的按位测试(num%3) == 0。

我可以将 num%2 替换为 num&1，但我仍然坚持使用 num%3 和逻辑或。

这个表达式也等同于 (num%2)*(num%3) == 0，但我不确定这有什么帮助。

Answer 1

是的，虽然它不是很漂亮，但您可以做一些类似于旧的“对所有十进制数字求和直到只剩下一个数字”的技巧来测试一个数字是否可以被 9 整除，除了二进制和被 整除3. 您也可以对其他数字使用相同的原则，但是许多基数/除数的组合会引入烦人的比例因子，因此您不再只是对数字求和。

反正16ⁿ-1是可以被3整除的，所以可以用radix 16，也就是四位求和。然后你只剩下一个半字节(好吧，实际上是 5 位)，你可以查一下。因此，例如在 C# 中(稍微测试过)编辑:经过蛮力测试，绝对有效

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;
}

---

我评论中的技巧，x * 0xaaaaaaab <= 0x55555555 ，通过模乘逆技巧工作。 0xaaaaaaab * 3 = 1 mod 2³²，这意味着 0xaaaaaaab * x = x / 3当且仅当
x % 3 = 0 . “如果”因为0xaaaaaaab * 3 * y = y (因为 1 * y = y )，所以如果 x形式为
3 * y然后它将映射回 y . “仅当”因为没有两个输入映射到相同的输出，所以所有不能被 3 整除的东西都将映射到比任何东西除以 3 所能得到的最高值更高的值(即 0xFFFFFFFF / 3 = 0x55555555 )。

您可以在 Division by Invariant Integers using Multiplication (T. Granlund and P. L. Montgomery) 中阅读更多相关信息(包括更通用的形式，其中包括旋转) .

你的编译器可能不知道这个技巧。例如这个:

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

成为 x64 的 Clang 3.4.1，

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

它应该是什么:

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