是否有一个明智的技巧来检查数字的可分性为2或3？
我正在寻找相当于(num%2) == 0 || (num%3) == 0逐位测试 (num%2) == 0 || (num%3) == 0 。
我可以用num&1替换num%2 ，但我仍然坚持使用num%3和逻辑 – 或者。
这个表达式也等同于(num%2)*(num%3) == 0 ，但我不确定这有多大帮助。
是的，虽然它不是很漂亮，你可以做一些类似于旧的“总和所有十进制数字，直到你只有一个左”的技巧来测试一个数字是否可被9整除，除了二进制和可分数为3。对于其他数字也可以使用相同的原理，但是基数/除数的许多组合会引入烦人的缩放因子，因此您不再只是求和数字。
无论如何，16 n -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 32 ，这意味着0xaaaaaaab * x = x / 3当且仅当
x % 3 = 0 。 “if”因为0xaaaaaaab * 3 * y = y （因为1 * y = y ），所以如果x是forms
3 * y然后它将映射回y 。 “只有”因为没有两个输入映射到同一个输出，所以不能被3整除的所有东西都会映射到高于你可以通过将任何东西除以3得到的最高值（即0xFFFFFFFF / 3 = 0x55555555 ）。
您可以使用乘法（T. Granlund和PL Montgomery）在不变整数除法中阅读更多相关信息（包括更一般的forms，包括旋转） 。
你编译器可能不知道这个技巧。 例如：
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
我想我参加这个派对有点晚了，但这里的解决方案比哈罗德的解决方案要快一点（而且稍微漂亮一点）：
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将通过在具有它们的架构（例如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的最接近的倍数小一个。）
在某些情况下，输入到以下步骤的数字将分别大于16位，8位和4位，但这不是问题，因为我们在向右移动时不会丢弃任何高位。