Bitshift w Javie

Question

Próbuję zrozumieć, jak działa bit shift. Czy ktoś mógłby wyjaśnić znaczenie tej linii:

while ((n&1)==0) n >>= 1; 

gdzie n jest liczbą całkowitą i dać mi przykład n gdy zmiana jest wykonywana.

Answer 1

Załóżmy, że n = 12. Bity dla tego będzie 1100 (1 * 8 + 1 * 4 + 0 * 2 + 0 * 1 = 12). Po raz pierwszy w pętli n & 1 == 0, ponieważ ostatnia cyfra 1100 wynosi 0, a kiedy I to, że z 1, otrzymujesz 0. Tak więc n >> = 1 spowoduje, że n zmieni się z 1100 (12) na 110 (6). Jak możesz zauważyć, przesuwanie w prawo ma ten sam efekt co dzielenie przez 2. Ostatni bit nadal wynosi zero, więc n & 1 nadal będzie wynosił 0, więc przesunie się jeszcze raz w prawo. n >> = 1 spowoduje przesunięcie kolejnej cyfry na prawą zmianę n z 110 (6) na 11 (3).

Teraz możesz zobaczyć, że ostatni bit to 1, więc n & 1 będzie 1, powodując przerwanie wykonywania pętli while. Celem pętli wydaje się przesunięcie liczby w prawo, aż znajdzie pierwszy włączony bit (aż wynik będzie nieparzysty).

Answer 2

n & 1 jest rzeczywiście bitowym operatorem AND. Tutaj wzór bitowy n będzie ORAZ w stosunku do wzoru bitowego 1. Kto będzie porównywany z wynikiem zerowym. Jeśli tak, to n jest przesunięte raz w prawo. Możesz przyjąć jedną prawą zmianę jako dzielenie przez 2 i tak dalej.

Answer 3

złamanie go:

n & 1 zrobi binarne porównania między n, a 1, która jest 00000000000000000000000000000001 w formacie binarnym. Jako taki, zwróci 00000000000000000000000000000001, gdy n kończy się na 1 (dodatnia parzyste lub ujemne liczby parzyste) i 00000000000000000000000000000000 w przeciwnym razie.

(n & 1) == 0 będzie zatem prawdziwe, jeśli n jest parzyste (lub nieparzyste nieparzyste), a fałszywe w przeciwnym razie.

n >> = 1 jest odpowiednikiem n = n >> 1. W związku z tym przesuwa wszystkie bity w prawo, co z grubsza odpowiada podziałowi o dwie (zaokrąglanie w dół).

Jeśli np. n rozpoczęte jako 12, a następnie w binarnym będzie to 1100. Po jednej pętli będzie 110 (6), po drugim będzie 11 (3), a następnie pętla zostanie zatrzymana.

Jeśli n wynosi 0, to po następnej pętli nadal będzie wynosić 0, a pętla będzie nieskończona.

Answer 4

na przykład, gdy N jest

n= b11110000 

następnie

n&1= b11110000 & 
     b00000001 
     --------- 
     b00000000 

n>>=1 b11110000 >> 1 
     --------- 
     b01111000 

n= b01111000 

jeżeli pętla nadal powinny być

n= b00001111 

Answer 5

Umożliwia n być 4 która binarny reprezentowany jest jako:

00000000 00000000 00000000 00000100 

(n&1) bitowo ands n z 1.
1 ma binarną reprezentację:

00000000 00000000 00000000 00000001 

Wynik logiczne jakiegokolwiek mnożenie jest 0:

00000000 00000000 00000000 00000100 = n 
00000000 00000000 00000000 00000001 = 1 
------------------------------------ 
00000000 00000000 00000000 00000000 = 0 

więc stan, gdy jest prawdziwe.
Skutecznie (n&1) został użyty do wydobycia najmniej znaczącego fragmentu z n.

W pętli while przesuń w prawo (>>) n przez 1. Prawe przesunięcie numeru o k jest takie samo, jak podzielenie liczby przez 2^k.

n który jest teraz 00000000 00000000 00000000 00000100 na prawej zmieniającym raz staje 00000000 00000000 00000000 00000010 który jest 2.

Następnie rozpakuj LSB (najmniej znaczący bit) z n ponownie co jest 0 i prawy shift znowu dać 00000000 00000000 00000000 0000001 który 1.

Następnie ponownie wyodrębniamy LSB z n, który jest teraz 1, a pętla zrywa.

Tak skutecznie utrzymać podzielenie liczby n przez 2 aż staje nieparzyste jak numery nieparzyste mają LSB zestawu.

Należy również pamiętać, że jeśli n jest 0 zacząć pójdziesz do nieskończonej pętli, ponieważ bez względu na to ile razy można podzielić 0 przez 2 nie będziesz dostać nieparzysta.

Answer 6

Załóżmy równa 42 (tylko dlatego)

int n = 42; 

while ((n & 1) == 0) { 
    n >>= 1; 
} 

iteracji 0:

• n = 42 (lub 0000 0000 0000 0000 0000 0000 0010 1010)
• n & 1 == 0 jest true (ze względu na brak & 1 = 0 lub 0000 0000 0000 0000 0000 0000 0000 0000)

Iteracja 1:

• n = 21 (lub 0000 0000 0000 0000 0000 0000 0001 0101)
• n & 1 == 0 jest false (bo n & 1 == 1 lub 0000 0000 0000 0000 0000 0000 0000 0001)

Co robi:

Zasadniczo, pętla dzieli n przez 2 dopóki n jest liczbą parzystą:

• n & 1 jest prosta kontrola parzystości,
• >> n = 1 przesunięcie bitów w prawo, który po prostu dzieli się przez 2.