if ((n & -n) == n) // i.e., n is a power of 2
// rest of the code
为什么会这样呢?
if ((n & -n) == n) // i.e., n is a power of 2
// rest of the code
为什么会这样呢?
因为在二进制补码中,-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.
(0 & -0) == 0
但是0不是2的幂。更好的说法是当n是2的幂、2的负幂或0时,((n & -n) == n)
成立。 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的负幂次方... 如顶部所述。
Random.java
文件。 - Mike Samueln
是什么类型;我还没有检查这个假设,但有点怀疑double
会表现出相同的方式。 - usern
的类型。在Java中,&
未定义为double
或float
类型,只定义为整数类型和布尔类型。由于布尔类型未定义-
运算符,因此我们可以安全地推断出n
是整数类型。 - Mike Samuel1 & 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。base 2 base 10
000001 = 1
000010 = 2
000100 = 4
...
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的幂次方,最不显著的比特位是唯一被设置的比特位。对于所有其他数字,存在多个比特位被设置,其中只有最不显著的比特位在结果中被设置。
这是关于2的幂及其二进制补码的属性。
例如,取8:
8 = 0b00001000
-8 = 0b11111000
计算二进制补码:
Starting: 0b00001000
Flip bits: 0b11110111 (one's complement)
Add one: 0b11111000
AND 8 : 0b00001000
简单来说,如果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
通过示例展示:
十六进制中的8 = 0x000008
十六进制中的-8 = 0xFFFFF8
8 & -8 = 0x000008
(n & (n - 1)) == 0
也适用(它会移除最低位比特,如果没有比特剩余,则原始数字中至多只有1个比特被设置)。 - harold