为什么（x＆3）与（x mod 4）相同？

我发现一些示例源代码，其中作者似乎使用按位运算符&而不是%运算符。但是，当我尝试x & 4时，它不会产生与x % 5相同的值。为什么（x＆3）与（x mod 4）相同？

2011-10-24 user385261

在过去，按位进行比模数快很多，所以对于两个幂来说这是一个很酷的“微优化”：） – TacticalCoder

@ user988052仍然是。在.NET（刚刚测试过）中速度提高了10％，代码在这里是http://ideone.com/BLqZP（但是请注意，在ideone上，差异要小得多）。发布+无调试器运行。 – xanatos

@ user988052：按位，并且比任何必须处理*全部*数字的通用'mod'实现仍然更快。但是这种优化是如此众所周知且很简单，以至于许多编译器都实现它，所以是的。 @xanatos：在进行基准测试时，一定要让JIT先热身。 – delnan

这仅适用于2.

权力一般：

x MOD 2^n

等同于：

x AND (2^n - 1)

另请注意，这可能仅适用于x >= 0是真实的，这取决于您的MOD的定义为x < 0。

要了解为什么这个工作的，考虑什么MOD真的是 - 它只是执行整数除法后余。在除以2^n的情况下，我们实际上只是将二进制值右移n位并丢弃任何移出的低位，例如，对于一个8位的二进制数

a b c d e f g h

如果我们通过除以4 = 2^2，则我们用2位右移：

0 0 a b c d e f

其余（g h）已被扔掉作为结果整数除法。

如果我们想知道余那么我们可以只通过应用0 0 0 0 0 0 1 1面具提取位g h：

a b c d e f g h 
AND 0 0 0 0 0 0 1 1 
    = 0 0 0 0 0 0 g h

注意，已经有值3，这在一般情况下只有2^n - 1.

让我们用一些实数来试试这个。假设我们要计算四分之四十二并同时获得商和余数：

42 = 0 0 1 0 1 0 1 0

要得到我们正确的2位移商：

42/4 (decimal) 
= 0 0 1 0 1 0 1 0 >> 2 
= 0 0 0 0 1 0 1 0 
= 10 (decimal) 

    42 MOD 4 (decimal) 
= 0 0 1 0 1 0 1 0 AND 0 0 0 0 0 0 1 1 
= 0 0 0 0 0 0 1 0 
= 2 (decimal)

所以42/4 = 10余2

来源

2011-10-24 13:30:04

答案很简单，试着用二进制来思考。

0000 = 0 AND 11 = 0000 = 0 
0001 = 1 AND 11 = 0001 = 1 
0010 = 2 AND 11 = 0010 = 2 
0011 = 3 AND 11 = 0011 = 3 
0100 = 4 AND 11 = 0000 = 0 
0101 = 5 AND 11 = 0001 = 1 
0110 = 6 AND 11 = 0010 = 2 
0111 = 7 AND 11 = 0011 = 3

...等等。

这与提醒的结果相同（％为余数，形式上不是模数）。它只适用于2的幂，只适用于零和正数。

来源

2011-10-24 13:34:33

为什么（x＆3）与（x mod 4）相同？

回答

相关问题