logo标签列表

为什么如果 (n & -n) == n，则 n 是 2 的幂？

javalogicbit-manipulation
84
2
新标签应该是一个提示。 :) - bzlm
10
这是答案链接：https://dev59.com/HnRB5IYBdhLWcg3wgXhV#600306。 - Jacob Mattison
2
跟随比特。顺便提一下，它也将零视为2的幂。公式(n & (n - 1)) == 0也适用（它会移除最低位比特，如果没有比特剩余，则原始数字中至多只有1个比特被设置）。 - harold
3
是的，我承认使用了这样的代码。只要你知道你正在处理二进制补码算术，并且明白各种转换和溢出陷阱，就可以进行许多类似的技巧。如果您想获得额外的学分，请尝试计算如何将数字上取整到下一个更高的2的幂次方，或者2的幂次方减1 - 在某些领域，这些操作需要惊人的频率。 - Hot Licks
1
等等，现在所有人都从java.util.Random源读取吗？（我几个月前读到过这个问题，自那以后在SO上记得有几个相关的问题。） - Mateen Ulhaq
7个回答
95

因为在二进制补码中，-n 等于 ~n+1。

如果 n 是2的幂，则只有一个位被设置。所以 ~n 除了那个位之外，所有位都被设置了。加上1，再次设置了这个特殊位，确保 n & (那个东西) 等于 n。

反过来也成立，因为前一行代码排除了0和负数。如果 n 有多个设置的位，则其中一个是最高位。这个位将不会被 +1 设置，因为有一个更低的清空位可以"吸收"它：

 n: 00001001000
~n: 11110110111
-n: 11110111000  // the first 0 bit "absorbed" the +1
        ^
        |
        (n & -n) fails to equal n at this bit.
48
描述并不完全准确，因为 (0 & -0) == 0 但是0不是2的幂。更好的说法是当n是2的幂、2的负幂或0时，((n & -n) == n)成立。
如果n是2的幂，则n在二进制中是一个1后面跟着若干个0。 -n在补码中是反码加1，所以位数对齐，如下：
 n      0000100...000
-n      1111100...000
 n & -n 0000100...000
为了理解这为什么有效，考虑二进制补码等于取反加一，即 -n == ~n + 1。
n          0000100...000
inverse n  1111011...111
                     + 1
two's comp 1111100...000

由于在加1以得到二进制补码时一直携带这个一，因此当n为2的幂次方时才能得到正确的结果。

如果n不是2的幂次方†，那么结果将缺少一位，因为由于该进位，二进制补码不会有最高位设置。

† - 或者零或2的负幂次方... 如顶部所述。

这里有一个技巧，可以隔离最不重要的1位。 - Hot Licks
2
关于(0 & -0) == 0，紧接着的语句是if (n <= 0) throw ...。这意味着在那个点上被测试的数字永远不会为0（或负数）。 - user
1
@Michael，非常正确。我回答的是标题中的问题，而不是批评我没有阅读过的Random.java文件。 - Mike Samuel
1
@Mike，我明白；然而，我认为代码注释中的陈述（包含在问题中并构成标题问题的基础）在没有上下文先决条件的情况下并不完全独立存在。如果你仅仅看这里发布的问题，我们甚至不知道n是什么类型；我还没有检查这个假设，但有点怀疑double会表现出相同的方式。 - user
3
@Michael，由于这个问题有“java”标签，我们可以很好地限制n的类型。在Java中，&未定义为double或float类型，只定义为整数类型和布尔类型。由于布尔类型未定义-运算符，因此我们可以安全地推断出n是整数类型。 - Mike Samuel
13
你需要将这些值视为位图，才能理解为什么这是正确的：
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

只有当两个字段都为1时，才会输出1。

现在，-n进行二进制补码操作。它将所有的0变为1并加上1。

7 = 00000111
-1 = NEG(7) + 1 = 11111000 + 1 = 11111001

然而

8 = 00001000
-8 = 11110111 + 1 = 11111000 

00001000  (8)
11111000  (-8)
--------- &
00001000 = 8.
只有当n为2的幂次方时，(n & -n) 才会等于n。
这是因为2的幂次方在二进制下只有一位是1，其他位都是0。 取反运算将得到完全相反的结果，为一串1中的单个0 (在原来1所在的位置)。加1将把低位的1移入0所在的位置。
按位与(&)运算将再次过滤掉1。
8
在二进制补码表示法中，关于2的幂次方的独特之处在于，它们由所有0位组成，除了第k位，其中n=2^k：
base 2    base 10
000001 =  1 
000010 =  2
000100 =  4
     ...

要得到补码中的负值，需要先将原数取反再加一。对于2的幂次方来说，这意味着在左侧获得一堆1，直到并包括正数中的那个1位，然后在右侧获得一堆0。
n   base 2  ~n      ~n+1 (-n)   n&-n  
1   000001  111110  111111      000001
2   000010  111101  111110      000010
4   000100  111011  111100      000100
8   001000  110111  111000      001000

您可以轻松看出，第2列和第4列的结果将与第2列相同。

如果您查看此图表中缺失的其他值，您会发现除了2的幂次方之外，这种情况不成立：

n   base 2  ~n      ~n+1 (-n)   n&-n  
1   000001  111110  111111      000001
2   000010  111101  111110      000010
3   000011  111100  111101      000001
4   000100  111011  111100      000100
5   000101  111010  111011      000001
6   000110  111001  111010      000010
7   000111  111000  111001      000001
8   001000  110111  111000      001000

对于n > 0的情况，n&-n只会有1个比特位被设置，而且该比特位将是n中最不显著的比特位。对于所有2的幂次方，最不显著的比特位是唯一被设置的比特位。对于所有其他数字，存在多个比特位被设置，其中只有最不显著的比特位在结果中被设置。

4

这是关于2的幂及其二进制补码的属性。

例如，取8：

8  = 0b00001000

-8 = 0b11111000

计算二进制补码：

Starting:  0b00001000
Flip bits: 0b11110111  (one's complement)
Add one:   0b11111000  

AND 8    : 0b00001000

对于2的幂次方，只有一个位被设置，因此添加将导致设置2^n的n个位（保持向n个位进位的那个位）。然后当您对两个数字进行AND运算时，您将得到原始数字。
对于不是2的幂次方的数字，其他位不会翻转，因此AND运算不会产生原始数字。
4

简单来说，如果n是2的幂次方，那就意味着只有一位是1，其他都是0：

00000...00001 = 2 ^ 0
00000...00010 = 2 ^ 1
00000...00100 = 2 ^ 2
00000...01000 = 2 ^ 3
00000...10000 = 2 ^ 4

and so on ...

因为-n是n的2的补码（这意味着唯一的为1的位将保持不变，而该位左侧的位被设置为1，实际上并不重要，因为AND运算符&的结果将为0，如果两个位中有一个为零）：

000000...000010000...00000 <<< n
&
111111...111110000...00000 <<< -n
--------------------------
000000...000010000...00000 <<< n
0

通过示例展示：

十六进制中的8 = 0x000008

十六进制中的-8 = 0xFFFFF8

8 & -8 = 0x000008

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接