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

Question

java.util.Random源代码294行说

if ((n & -n) == n) // i.e., n is a power of 2
    // rest of the code

为什么是这样？

Answer 1

因为在2的补码中,-n是~n+1.

如果n是2的幂,那么它只有一位设置.因此,~n具有设定,除了一个在所有位.添加1,然后再次设置特殊位,确保n & (that thing)等于n.

反过来也是如此,因为在该Java源代码中,前一行排除了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.

Answer 2

描述并不完全准确,因为(0 & -0) == 00不是2的幂.更好的说法是

((n & -n) == n) 当n是2的幂,或2的幂的负,或零.

如果n是2的幂,则二进制中的n是单个1,后跟零.-in的二进制补码是反+ 1,因此这些位排成一行

 n      0000100...000
-n      1111100...000
 n & -n 0000100...000

要了解为什么这项工作,请将二进制补码视为反+ 1, -n == ~n + 1

n          0000100...000
inverse n  1111011...111
                     + 1
two's comp 1111100...000

因为你在添加一个以获得两个补码时一直带着它.

如果n不是2的幂†那么结果将会丢失一点,因为由于该进位,二进制补码不会具有最高位设置.

† - 或零或2的幂的负数...如顶部所述.

Answer 3

您需要将值视为位图,以了解为什么这是真的:

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

所以只有当两个字段都是1时才会出现1.

现在-n做了2的补码.它将所有内容更改0为1并添加1.

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

然而

8 = 00001000
-8 = 11110111 + 1 = 11111000 

00001000  (8)
11111000  (-8)
--------- &
00001000 = 8.

只有2的幂才是(n & -n)n.
这是因为2的幂表示为零的长海中的单个设置位.否定将产生完全相反的,在1的海洋中产生单个零(在曾经是 1的位置).添加1会将较低的一个移动到零所在的空间.
按位和(&)将再次过滤掉1.

Answer 4

在二进制补码表示中,关于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列相同.

如果你看一下这个图表中缺少的其他值,你就可以看出为什么除了两个权力之外的其他任何东西都没有:

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&-n将(对于n> 0)仅设置1位,该位将是n中的最低有效位.对于所有2的幂次数,最低有效设置位是唯一的设置位.对于所有其他数字,有多个位集,其中只有最低有效位将在结果中设置.