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

Question

Line 294 java.util.Random source says

if ((n & -n) == n) // ie, n is a power of 2 // rest of the code 

Why is this?

Answer 1

The description is not entirely accurate, because (0 & -0) == 0 , but 0 is not the power of two. Better say that it

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

If n is a power of two, then n in binary is the only 1 followed by zeros. -n in two additions is the inverse of + 1, so the bits are aligned in this way

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

To understand why this work, we consider two additions as inverse + 1, -n == ~n + 1

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

since you carry one all the way, adding it to get two additions.

If n was anything other than the power of two daggers; then the result will be absent, because the two most significant bits will not have the most significant bit set due to transfer.

& cross - either zero or negative of the power of two ... as explained at the top.

Answer 2

Because in 2 additions -n there is ~n+1 .

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

The converse is also true because 0 and negative numbers were excluded by the previous line in this Java source. If n has more than one bit, then one of them is the highest such bit. This bit will not be set with +1 , because it has a lower 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. 

Answer 3

You need to look at the values ​​like 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 equal to 1, 1 is returned.

Now - has 2 additions. It changes all 0 to 1 and 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 degrees 2 will (n & -n) be n.
This is due to the fact that power 2 is represented as a single bit in a long sea of ​​zeros. Denial will give the exact opposite, one zero (in the place where it used to be 1) in the sea of ​​the 1st. Adding 1 will shift the lower ones to the space where the zero is.
Both Bitwise and (&) filter again 1.

Answer 4

In two additional representations, the only thing about the 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 additions, you flip all the bits and add them. For powers of two, this means that you get a bunch of 1 with left and up to 1 bit, which was in a positive value, and then a bunch of 0 with 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 columns 2 and 4 will be the same as column 2.

If you look at other values ​​that are not in this graph, you can understand why this is not done for anything but 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 1 bit be set ever, and this bit will be the least significant set bit in n. For all numbers that are powers of two, the least significant bit of the set is the only bit set. For all other numbers, there is more than one bit set, from which only the smallest value will be specified as a result.

Answer 5

This is a property of degrees 2 and their two complements .

For example, take 8:

 8 = 0b00001000 -8 = 0b11111000 

Calculation of two additions:

 Starting: 0b00001000 Flip bits: 0b11110111 (one complement) Add one: 0b11111000 AND 8 : 0b00001000 

For powers of 2, only one bit will be set , so adding will result in the bit n ^th of 2 ⁿ being set (one carries on the bit n ^th ). Then, when you AND two numbers, you get the original.

For numbers that are not powers of 2, the other bits will not be flipped, so AND does not give the original number.

Answer 6

Simply, if n is a power of 2, which means that only one bit is set to 1 and the rest is 0:

 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 2 additions to n (this means that the only bit that is 1 remains as it is, and the bits on the left side of this bit sit to 1, which does not really matter, since the result 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 

Answer 7

Example:

8 in hex = 0x000008

-8 in hex = 0xFFFFF8

8 and -8 = 0x000008