Why if (n & -n) == n then n is a power of 2?

Because in 2’s complement, -n is ~n+1.

If n is a power of 2, then it only has one bit set. So ~n has all the bits set except that one. Add 1, and you set the special bit again, ensuring that n & (that thing) is equal to n.

The converse is also true because 0 and negative numbers were ruled out by the previous line in that Java source. If n has more than one bit set, then one of those is the highest such bit. This bit will not be set by the +1 because there’s a lower clear bit to “absorb” it:

 n: 00001001000
~n: 11110110111
-n: 11110111000  // the first 0 bit "absorbed" the +1
        ^
        |
        (n & -n) fails to equal n at this bit.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)