我正在寻找相当于(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位 – 开头只需要一个额外的步骤。
最后两行显然是无耻地从哈罗德的解决方案中获得的(很好的一个,我不会那么优雅地做到这一点)。
可能的进一步优化:
前四个步骤基于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位,但这不是问题,因为我们在向右移动时不会丢弃任何高位。
以上就是c/c++开发分享是否有一个明智的技巧来检查数字的可分性为2或3?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/562077.html