是否有一个通过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整除,因此您可以使用基数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;
}

在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

应该是什么:

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

Answer 2

我想我参加这个派对有点晚了,但这里的解决方案比哈罗德的解决方案要快一点(而且稍微漂亮一点):

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位 - 开头只需要一个额外的步骤.

最后两行显然是无耻地从哈罗德的解决方案中获取的(很好的一个,我不会那么优雅地做到这一点).

可能的进一步优化:

• 所述&在前两个步骤OPS将通过仅仅使用在具有它们(86,例如)架构下半寄存器被优化掉.
• 第三步的最大可能输出是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的最接近的倍数小一个.)

在某些情况下,输入到以下步骤的数字将分别大于16位,8位和4位,但这不是问题,因为我们在右移时不会丢弃任何高位.