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

Question

Line 294 of java.util.Random source说

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.