为什么（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

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

((n & -n) == n) 当n是2的幂或2的幂的负数或零时。

如果n是2的幂，则二进制中的n是单个1，后跟零。-n为2的补数是倒数+ 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的幂的负数…如顶部所述。