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

Question

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

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

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

Answer 1

是的，虽然它不是很漂亮，但您可以做一些类似于旧的 "sum all the decimal digits until you have only one left" 技巧的事情来测试一个数字是否可以被 9 整除，二进制和被 3 整除除外。您可以使用其他数字也采用相同的原理，但是 base/divisor 的许多组合引入了烦人的比例因子，因此您不再只是对数字求和。

反正16ⁿ-1能被3整除，所以可以用基数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 通过 mod 元乘法逆技巧起作用。 0xaaaaaaab * 3 = 1 mod 2³²，这意味着 0xaaaaaaab * x = x / 3 当且仅当
x % 3 = 0。 "if" 因为 0xaaaaaaab * 3 * y = y （因为 1 * y = y），所以如果 x 的形式是
3 * y 然后它将映射回 y。 "only if" 因为没有两个输入映射到相同的输出，所以所有不能被 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;
}

在 Clang 3.4.1 for x64 上变为

movl    %edi, %eax
movl    63311531, %ecx       # imm = 0xAAAAAAAB
imulq   %rax, %rcx
shrq    , %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

Answer 2

我想我来晚了一点，但这里有一个比 harold 的解决方案更快（也更漂亮）的解决方案：

bool is_multiple_of_3(std::uint32_t i)
{
    i = (i & 0x0000FFFF) + (i >> 16);
    i = (i & 0x00FF) + (i >> 8);
    i = (i & 0x0F) + (i >> 4);
    i = (i & 0x3) + (i >> 2);
    const std::uint32_t lookuptable = 0x49249249;
    return ((lookuptable >> i) & 1) != 0;
}

它是 C++11，但这对这段代码来说并不重要。它还针对 32 位无符号整数进行了蛮力测试。它为前四个步骤中的每一个步骤至少节省了一个位摆弄操作。它还可以很好地扩展到 64 位——开始时只需要一个额外的步骤。

最后两行显然是无耻地取自 harold 的解决方案（不错，我不会那么优雅地这样做）。

可能的进一步优化：

前两步中的 & 操作将通过仅使用具有它们的体系结构（例如 x86）上的下半部分寄存器来优化。
第三步的最大可能输出是 60，第四步的最大可能输出是 15（当函数参数是 0xFFFFFFFF 时）。鉴于此，我们可以省略第四步，使用 64 位 lookuptable 并直接转移到第三步之后的那个。这对于 32 位模式下的 Visual C++ 2013 来说是个坏主意，因为右移变成了对执行大量测试和跳转的代码的非内联调用。但是，如果 64 位寄存器本身就可用，那应该是个好主意。
如果将函数修改为采用 64 位参数，则需要重新评估上述观点。最后两步的最大输出（在开始时添加一步后将是第 4 步和第 5 步）将分别为 75 和 21，这意味着我们无法再消除最后一步。

前四步是基于一个32位数可以写成

(high 16 bits) * 65536 + (low 16 bits) = 
(high 16 bits) * 65535 + (high 16 bits) + (low 16 bits) = 
(high 16 bits) * 21845 * 3 + ((high 16 bits) + (low 16 bits))

所以当且仅当右括号可以被 3 整除时，整个事情才能被 3 整除。依此类推，因为这适用于 256 = 85 * 3 + 1、16 = 5 * 3 + 1 和 4 = 3 + 1. （当然，这通常适用于 2 的偶次方；奇数次方比最接近的 3 的倍数小 1。）

在某些情况下，输入到以下步骤中的数字将分别大于 16 位、8 位和 4 位，但这不是问题，因为我们不会降低任何高-右移时排序位。

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

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

c

c++

python

java

bit-manipulation