c/c++语言开发共享是否有一个明智的技巧来检查数字的可分性为2或3？

是的，虽然它不是很漂亮，你可以做一些类似于旧的“总和所有十进制数字，直到你只有一个左”的技巧来测试一个数字是否可被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是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位 – 开头只需要一个额外的步骤。

最后两行显然是无耻地从哈罗德的解决方案中获得的（很好的一个，我不会那么优雅地做到这一点）。

可能的进一步优化：

前四个步骤基于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位，但这不是问题，因为我们在向右移动时不会丢弃任何高位。