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

小开

最佳答案

The description is not entirely accurate because (0 & -0) == 0 but 0 is not a power of two. A better way to say it is

((n & -n) == n) when n is a power of two, or the negative of a power of two, or zero.

If n is a power of two, then n in binary is a single 1 followed by zeros. -n in two's complement is the inverse + 1 so the bits lines up thus

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

To see why this work, consider two's complement as inverse + 1, -n == ~n + 1

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

since you carry the one all the way through when adding one to get the two's complement.

If n were anything other than a power of two† then the result would be missing a bit because the two's complement would not have the highest bit set due to that carry.

† - or zero or a negative of a power of two ... as explained at the top.

小开

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.

小开

Shown through example:

8 in hex = 0x000008

-8 in hex = 0xFFFFF8

8 & -8 = 0x000008

小开

You need to look at the values as bitmaps to see why this is true:

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

So only if both fields are 1 will a 1 come out.

Now -n does a 2's complement. It changes all the 0 to 1 and it adds 1.

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

However

8 = 00001000
-8 = 11110111 + 1 = 11111000


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

Only for powers of 2 will (n & -n) be n.
This is because a power of 2 is represented as a single set bit in a long sea of zero's. The negation will yield the exact opposite, a single zero (in the spot where the 1 used to be) in a sea of 1's. Adding 1 will shift the lower ones into the space where the zero is.
And The bitwise and (&) will filter out the 1 again.

小开

It's property of powers of 2 and their two's complement.

For example, take 8:

8  = 0b00001000


-8 = 0b11111000

Calculating the two's complement:

Starting:  0b00001000
Flip bits: 0b11110111  (one's complement)
Add one:   0b11111000


AND 8    : 0b00001000

For powers of 2, only one bit will be set so adding will cause the n^th bit of 2ⁿ to be set (the one keeps carrying to the n^th bit). Then when you AND the two numbers, you get the original back.

For numbers that aren't powers of 2, other bits will not get flipped so the AND doesn't yield the original number.

小开

Simply, if n is a power of 2 that means only one bit is set to 1 and the others are 0's:

00000...00001 = 2 ^ 0
00000...00010 = 2 ^ 1
00000...00100 = 2 ^ 2
00000...01000 = 2 ^ 3
00000...10000 = 2 ^ 4


and so on ...

and because -n is a 2's complement of n (that means the only bit which is 1 remains as it is and the bits on left side of that bit are sit to 1 which is actually doesn't matter since the result of AND operator & will be 0 if one of the two bits is zero):

000000...000010000...00000 <<< n
&
111111...111110000...00000 <<< -n
--------------------------
000000...000010000...00000 <<< n

小开

In two's complement representation, the unique thing about powers of two, is that they consist of all 0 bits, except for the kth bit, where n = 2^k:

base 2    base 10
000001 =  1
000010 =  2
000100 =  4
...

To get a negative value in two's complement, you flip all the bits and add one. For powers of two, that means you get a bunch of 1s on the left up to and including the 1 bit that was in the positive value, and then a bunch of 0s on the right:

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

You can easily see that the result of column 2 & 4 is going to be the same as column 2.

If you look at the other values missing from this chart, you can see why this doesn't hold for anything but the powers of two:

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 will (for n > 0) only ever have 1 bit set, and that bit will be the least significant set bit in n. For all numbers that are powers of two, the least significant set bit is the only set bit. For all other numbers, there is more than one bit set, of which only the least significant will be set in the result.