(n & -n) == n이면 n이 2의 거듭 제곱 인 이유는 무엇입니까?

(n & -n) == n이면 n이 2의 거듭 제곱 인 이유는 무엇입니까?

---

java.util.Random의 소스 라인 (294)은 말한다

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

왜 이런거야?

---

(0 & -0) == 00이 2의 거듭 제곱이 아니기 때문에 설명이 완전히 정확 하지는 않습니다. 그것을 말하는 더 좋은 방법은

((n & -n) == n) n이 2의 거듭 제곱이거나 2의 제곱 또는 0의 음수 일 때.

n이 2의 거듭 제곱이면 이진수의 n은 단일 1 다음에 0이 오는 것입니다. 2의 보수에서 -n은 역 + 1이므로 비트가 정렬됩니다.

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

이 작업이 왜 작동하는지 알아 보려면 2의 보수를 역 + 1로 간주하고 -n == ~n + 1

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

2의 보수를 얻기 위해 하나를 추가 할 때 하나를 끝까지 가지고 있기 때문입니다.

n이 2의 거듭 제곱 † 이외의 값이면 2의 보수가 해당 캐리로 인해 가장 높은 비트 세트를 갖지 않기 때문에 결과에 비트가 누락됩니다.

†-또는 2의 제곱의 0 또는 음수 ... 위에 설명 된대로.

---

때문에 2의 보수에 -n있다 ~n+1.

n가 2의 거듭 제곱 이면 1 비트 만 설정됩니다. 그래서 ~n그 비트를 제외한 모든 비트가 설정되었습니다. 하나를 추가하면 그 보장, 다시 특별 비트를 설정 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.

---

이것이 사실 인 이유를 확인하려면 값을 비트 맵으로보아야합니다.

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

따라서 두 필드가 모두 1 인 경우에만 1이 나옵니다.

이제 -n은 2의 보수를합니다. 이 모든 변화 0에 1그리고 1을 추가합니다.

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

하나

8 = 00001000
-8 = 11110111 + 1 = 11111000 

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

2의 거듭 제곱에 대해서만 (n & -n)n이됩니다.
이것은 2의 거듭 제곱이 0의 긴 바다에서 단일 세트 비트로 표현되기 때문입니다. 부정은 1의 바다에서 정반대의 단일 0 (1이 있던 자리에) 을 산출합니다 . 1을 더하면 낮은 값이 0이있는 공간으로 이동합니다.
그리고 비트 및 (&)는 1을 다시 필터링합니다.

---

2의 보수 표현에서 2의 거듭 제곱에 대한 독특한 점은 n = 2 ^ k 인 k 번째 비트를 제외하고 모두 0 비트로 구성된다는 것입니다.

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.

---

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

---

Shown through example:

8 in hex = 0x000008

-8 in hex = 0xFFFFF8

8 & -8 = 0x000008

참고URL : https://stackoverflow.com/questions/7405438/why-if-n-n-n-then-n-is-a-power-of-2