是否有按位的技巧来检查数字的2或3的可除性? [英] Is there a bit-wise trick for checking the divisibility of a number by 2 or 3?

问题描述

我正在寻找与(num%2) == 0 || (num%3) == 0等效的按位测试.

我可以将num%2替换为num&1，但是我仍然对num%3和逻辑或保持不变.

此表达式也等效于(num%2)*(num%3) == 0，但是我不确定这有什么帮助.

解决方案

是的，虽然不是很漂亮，但您可以做一些类似于旧的将所有十进制数字加起来，直到只剩下一个"的技巧来测试是否一个数字可被9整除，但二进制形式可被3整除.您也可以对其他数字使用相同的原理，但是基数/除数的许多组合引入了令人讨厌的缩放因子，因此您不再只是求和数字了./p>

无论如何，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通过模块化乘法逆向技巧起作用. 0xaaaaaaab * 3 = 1 mod 2 ³² ，这表示0xaaaaaaab * x = x / 3当且仅当
x % 3 = 0. "if"，因为0xaaaaaaab * 3 * y = y(因为1 * y = y)，所以如果x的形式为
3 * y，则它将映射回y. 仅当"，因为没有两个输入映射到相同的输出，因此所有不能被3整除的事物都将映射为比通过除以3(0xFFFFFFFF / 3 = 0x55555555)得到的最高事物更高的事物.

您可以在使用乘法(T. Granlund和PL 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

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.

解决方案

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ⁿ-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³², 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

这篇关于是否有按位的技巧来检查数字的2或3的可除性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！