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

Linia 294 od źródła java.util.Random mówi

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

Dlaczego to?

Opis nie jest całkowicie dokładny, ponieważ (0 & -0) == 00 nie jest potęgą dwójki. Lepszy sposób, żeby to powiedzieć

((n & -n) == n) kiedy n jest potęgą dwóch lub minusem potęgi dwóch lub zerem.

Jeśli n jest potęgą dwóch, to n w systemie binarnym to pojedyncze 1, po którym następują zera. -n w uzupełnieniu do dwóch jest odwrotnością + 1, więc bity są wyrównane w ten sposób

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

Aby zobaczyć, dlaczego to działa, rozważ uzupełnienie do dwóch jako odwrotność + 1, -n == ~n + 1

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

ponieważ prowadzisz jeden przez całą drogę, dodając jeden, aby uzyskać uzupełnienie do dwóch.

Gdyby n było czymkolwiek innym niż potęgą dwóch †, wynik byłby trochę zabraknięty, ponieważ dopełnienie dwóch nie miałoby ustawionego najwyższego bitu z powodu tego przeniesienia.

† - lub zero lub minus potęgi dwóch ... jak wyjaśniono na górze.

Ponieważ w uzupełnieniu 2 -njest ~n+1.

Jeśli njest potęgą 2, to ma ustawiony tylko jeden bit. Więc ~nma ustawione wszystkie bity oprócz tego jednego. Dodaj 1 i ponownie ustaw specjalny bit, upewniając się, że n & (that thing)jest równy n.

Odwrotna sytuacja jest również prawdą, ponieważ w poprzednim wierszu tego źródła Java wykluczono liczby 0 i ujemne. Jeśli nma więcej niż jeden ustawiony bit, to jeden z nich jest najwyższym takim bitem. Ten bit nie zostanie ustawiony przez, +1ponieważ istnieje niższy przezroczysty 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 mapy bitowe, aby zobaczyć, dlaczego tak jest:

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

Więc tylko jeśli oba pola mają wartość 1, wyjdzie 1.

Teraz -n dopełnia 2. To zmienia wszystko 0, aby 1i to dodaje 1.

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

jednak

8 = 00001000
-8 = 11110111 + 1 = 11111000 

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

Tylko dla potęg 2 będzie (n & -n)n.
Dzieje się tak, ponieważ potęga 2 jest reprezentowana jako pojedynczy zestaw bitów w długim morzu zer. Negacja da dokładnie odwrotność, pojedyncze zero (w miejscu, gdzie kiedyś było 1) w morzu jedynek. Dodanie 1 przesunie niższe z nich w przestrzeń, w której jest zero.
A bitowe i (&) ponownie odfiltrują 1.

W reprezentacji dopełnienia do dwóch, unikalną cechą potęg dwójki jest to, że składają się one ze wszystkich 0 bitów, z wyjątkiem k-tego bitu, gdzie n = 2 ^ k:

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

Aby uzyskać ujemną wartość w uzupełnieniu do dwóch, odwróć wszystkie bity i dodaj jeden. Dla potęgi dwójki oznacza to, że otrzymujesz pęczek jedynek po lewej stronie do 1 bitu, który był w wartości dodatniej, a następnie kilka zer 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żesz łatwo zobaczyć, że wynik z kolumny 2 i 4 będzie taki sam, jak w kolumnie 2.

Jeśli spojrzysz na inne wartości, których brakuje na tym wykresie, zobaczysz, dlaczego nie dotyczy to niczego 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 (dla n> 0) zawsze mieć ustawiony tylko 1 bit, a ten bit będzie najmniej znaczącym ustawionym bitem w n. Dla wszystkich liczb, które są potęgami dwójki, najmniej znaczący ustawiony bit jest jedynym ustawionym bitem. Dla wszystkich innych liczb jest więcej niż jeden zestaw bitów, z których tylko najmniej znaczący zostanie ustawiony w wyniku.

Jest to właściwość potęg 2 i ich dopełnienia .

Na przykład weź 8:

8  = 0b00001000

-8 = 0b11111000

Obliczanie dopełnienia do dwóch:

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

AND 8    : 0b00001000

Dla potęg 2, zostanie ustawiony tylko jeden bit, więc dodanie spowoduje ustawienie n- ^tego bitu o wartości 2 ⁿ (ten przenosi do n- ^tego bitu). Następnie, gdy zdobędziesz ANDdwie liczby, otrzymasz oryginał z powrotem.

W przypadku liczb, które nie są potęgami 2, inne bity nie zostaną odwrócone, więc ANDnie dają oryginalnej liczby.

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

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

and so on ...

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

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

Pokazano na przykładzie:

8 w formacie szesnastkowym = 0x000008

-8 w zapisie szesnastkowym = 0xFFFFF8

8 & -8 = 0x000008