Dlaczego jeśli (n & -n) == n to N jest potęgą 2?

Ponieważ w dopełniaczu 2 -n jest ~n+1.

Jeśli n jest potęgą 2, to ma tylko jeden bit ustawiony. Więc ~n ma ustawione wszystkie bity oprócz tego. Dodajemy 1 i ustawiamy bit specjalny ponownie, upewniając się, że {[5] } jest równe n.

Konwersja jest również prawdziwa, ponieważ liczby 0 i ujemne zostały wykluczone przez poprzedni wiersz w tym źródle Javy. Jeśli {[3] } ma więcej niż jeden bit ustawiony, to jeden z nich jest najwyższym takim bitem. Ten bit Nie będzie ustawiony przez +1 ponieważ jest niższy czysty bit, aby go "wchłonąć":

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

Musisz spojrzeć na wartości jako bitmapy, aby zobaczyć, dlaczego jest to prawda:

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

Więc tylko jeśli oba pola są 1, wyjdzie 1.

Now-n robi dopełniacz 2. Zmienia wszystkie 0 na 1 i dodaje 1.

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

Jednakże

8 = 00001000
-8 = 11110111 + 1 = 11111000 

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

Tylko dla potęg 2 (n & -n) będzie n.
Wynika to z faktu, że moc 2 jest reprezentowana jako pojedynczy Bit set w długim morzu zera. Negacja daje dokładnie odwrotne, pojedyncze zero (w miejscu, gdzie 1 kiedyś) w morzu 1. dodanie 1 spowoduje przesunięcie dolnych w przestrzeń, w której jest zero.
A bitowe i ( & ) ponownie odfiltrowują 1.

W reprezentacji dopełniacza dwójki wyjątkową rzeczą o potęgach dwójki jest to, że składają się one ze wszystkich 0 bitów, z wyjątkiem bitu kth, gdzie n = 2^k:

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

Aby uzyskać ujemną wartość w dopełniaczu dwójki, odwracasz wszystkie bity i dodajesz jeden. Dla potęg dwóch oznacza to, że otrzymujesz kilka 1s po lewej stronie do 1 bitu włącznie, który był w wartości dodatniej, a następnie kilka 0s po prawej:

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

Można łatwo zobaczyć, że wynik Kolumny 2 i 4 będzie być takie same jak Kolumna 2.

Jeśli spojrzysz na inne wartości brakujące na tym wykresie, możesz zobaczyć, dlaczego nie ma to nic poza potęgami dwóch:

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 będzie miało (dla n > 0) tylko 1 bit ustawiony, a ten bit będzie najmniej znaczącym bitem ustawionym w N. dla wszystkich liczb, które są potęgami dwóch, najmniej znaczącym bitem ustawionym jest jedyny ustawiony bit. Dla wszystkich pozostałych liczb istnieje więcej niż jeden zestaw bitów, z których tylko najmniej znaczący będzie ustawiony w wynik.

Jest własnością potęg 2 i ich dopełnienia dwójki .

Na przykład, weźmy 8:

8  = 0b00001000

-8 = 0b11111000

Obliczanie dopełnienia obu:

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

AND 8    : 0b00001000

Dla potęg 2, tylko jeden bit zostanie ustawiony, więc dodanie spowoduje ustawienie n ^th bitu 2ⁿ (ten przenosi się do N ^th bit). Wtedy, gdy ty AND dwie cyfry, dostajesz oryginał z powrotem.

Dla liczb, które nie są potęgami 2, inne bity nie otrzymają AND nie daje oryginalnej liczby.

Po prostu, jeśli N jest potęgą 2, oznacza to, że tylko jeden bit jest ustawiony na 1, a pozostałe na 0:

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

and so on ...

I Ponieważ -n jest dopełnieniem 2 n (to oznacza, że jedyny bit, który jest 1, pozostaje taki, jaki jest, a bity po lewej stronie tego bitu są siedzące do 1, co w rzeczywistości nie ma znaczenia, ponieważ wynik operatora AND & będzie równy 0, jeśli jeden z dwóch bitów jest równy zeru):

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

Pokazane przez przykład:

8 W hex = 0x000008

-8 W hex = 0xfffff8

8 & -8 = 0x000008