如何仅使用逻辑运算符AND来判断数字是否是四的倍数？

Question

我正在搞乱汇编语言编程,我很好奇我如何使用逻辑运算符AND来判断数字是否为4的倍数？

我知道如何使用"div"或"remaining"指令来完成它,但我试图用数字/字的位操作来做到这一点.

谁能指出我正确的方向？我正在使用MIP,但语言无关的答案很好.

Answer 1

好吧,要检测一个数字是否是另一个的倍数,你只需要做x MOD y.如果结果是0,则它是偶数倍.

对于每y一个力量而言2,它(x MOD y)也是等同于(x AND (y - 1)).

因此:

IF (x AND 3) == 0 THEN
    /* multiple of 4 */

编辑:

好的,你想知道为什么 (x MOD y) == (x AND (y - 1))什么时候y是2的力量.我会尽力解释.

基本上,如果一个数是2的幂,那么它有一个单位设置(因为二进制是基数2).这意味着所有低位都未设置.例如:16 == 10000b, 8 == 1000b等等

如果从这些值中的任何一个中减去1.你最终得到的是未设置的位,并且它下面的所有位都被置位.

15 = 01111b, 7 = 0111b所以基本上它创建了一个掩码,可以用来测试是否设置了任何低位.我希望这很清楚.

编辑: BastienLéonard的评论也涵盖了它:

如果将(无符号)除以4,则向右移两位.因此剩余部分是那两个比特,当你分裂时会丢失.4 - 1 = 11b,也就是说,当你用一个值和它时,产生两个最右边的位的掩码.

编辑:请参阅此页面以获得更清晰的解释:http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_positive_number_is_a_power_of_two.

它涵盖了2的检测功率,如果功率为2,则使用AND作为快速模运算.

Answer 2

(x & 3) == 0

Wrt 汇编语言，如果可用，使用 TST，否则使用 AND，并检查零标志。