Operacje bitowe, część 2

1. Bitowe przesunięcie w lewo

Java ma również 3 operatory przesunięcia bitowego : Jeśli naprawdę potrzebujesz, możesz po prostu przesunąć wszystkie bity liczby o kilka pozycji w lewo lub w prawo.

Aby przesunąć bity liczby w lewo, potrzebujesz operatora przesunięcia bitowego w lewo . Tak to jest napisane:

a << b

Gdzie ato liczba, której bity są przesuwane, a bto liczba wskazująca, ile razy należy przesunąć bity liczby aw lewo. Podczas tej operacji bity niższego rzędu dodane po prawej stronie są zerami.

Przykłady:

0b00000011 << 1

0b00000110

0b00000011 << 2

0b00001100

0b00000011 << 5

0b01100000

0b00000011 << 20

0b001100000000000000000000

Przesunięcie o jedną cyfrę w lewo daje taki sam efekt, jak pomnożenie liczby przez 2.

Chcesz pomnożyć liczbę przez 16? 16 to to samo co 2 ⁴ . Więc przesuwasz cyfrę o 4 cyfry w lewo

2. Bitowe przesunięcie w prawo

Bity można również przesuwać w prawo. Aby to zrobić, użyj operatora przesunięcia bitowego w prawo . Tak to jest napisane:

a >> b

Gdzie ajest liczba, której bity są przesuwane, oraz bliczba przesunięć bitów liczby aw prawo.

Przykłady:

0b11000011 >> 1

0b01100001

0b11000011 >> 2

0b00110000

0b11000011 >> 5

0b00000110

0b11000011 >> 20

0b00000000

Przesunięcie o jedną cyfrę w prawo ma taki sam efekt jak podzielenie liczby przez 2.

Podczas tej operacji bity wyższego rzędu dodane po lewej stronie są zerami, ale nie zawsze !

Podczas przesuwania bitów liczby w prawo wartość bitu znaku zwykle również się przesuwa, a znak liczby zostaje utracony. W związku z tym dla liczb ujemnych (gdzie skrajny lewy bit to 1) ten bit jest traktowany w specjalny sposób. Podczas przesuwania bitów liczby w prawo, a 0jest dodawane po lewej stronie, jeśli skrajny lewy bit to 0, a a 1jest dodawane po lewej stronie, jeśli najbardziej wysunięty na lewo bit to 1.

Ale w powyższym przykładzie nie wydaje się to być wynikiem. Dlaczego? Ponieważ literały całkowite to ints i  faktycznie oznaczają . Oznacza to, że skrajny lewy bit ma wartość zero.0b111111110b00000000000000000000000011111111

Wielu programistów jest sfrustrowanych tym zachowaniem związanym z przesunięciem w prawo i woleliby, aby liczba zawsze była dopełniana zerami. Więc Java dodał kolejny prawy operator przesunięcia .

Tak to jest napisane:

a >>> b

Gdzie a jest liczba, której bity są przesuwane, oraz b  liczba przesunięć bitów liczby aw prawo. Ten operator zawsze dodaje zera po lewej stronie, niezależnie od oryginalnej wartości bitu znaku liczby a.

3. Praca z flagami

Programiści stworzyli niemal całkowicie nowy kierunek studiów oparty na operacjach bitowych i przesunięciach: pracę z flagami.

Kiedy komputery miały bardzo mało pamięci, bardzo popularne było umieszczanie wielu informacji w jednej liczbie. Liczba została potraktowana jako tablica bitów: int to 32 bity, a long to 64 bity.

W takiej liczbie można zapisać wiele informacji, zwłaszcza jeśli trzeba przechowywać wartości logiczne ( truelub ). falsePojedynczy longjest jak booleantablica złożona z 64 elementów. Bity te nazwano flagami i manipulowano nimi za pomocą następujących operacji:

• ustawić flagę
  (zrób określony bit równy 1)
• zresetuj flagę
  (zrób określony bit równy 0)
• sprawdź flagę
  (sprawdź wartość konkretnego bitu)

A oto jak to się robi z operatorami bitowymi.

Ustawianie flagi

Aby ustawić określony bit na 1, musisz wykonać bitową operację OR między liczbą, której bit chcesz ustawić, a specjalnie utworzoną liczbą, gdzie tylko ten bit to 1.

Załóżmy na przykład, że masz numer 0b00001010i musisz ustawić piąty bit na 1. W takim przypadku musisz:

0b00001010 | 0b00010000 = 0b00011010

Gdyby piąty bit był już ustawiony na jeden, nic by się nie zmieniło.

Ogólnie operację ustawiania flagi można zapisać w następujący sposób

a | (1 << b)

Gdzie a jest liczba, której bit zostanie ustawiony na 1. I b jest położeniem bitu do ustawienia. Użycie operatora przesunięcia w lewo jest tutaj bardzo wygodne, ponieważ od razu można stwierdzić, z którym bitem pracujemy.

Resetowanie flagi

Aby zresetować określony bit (czyli ustawić go na 0) bez zakłócania innych bitów, należy wykonać operację &pomiędzy liczbą, której bit chcesz zresetować (czyli ustawić na 0) a specjalnie utworzoną liczbą, w której wszystkie bity są równe 1oprócz dla bitu, który chcesz zresetować.

Załóżmy na przykład, że masz numer 0b00001010i musisz ustawić czwarty bit na 0. W takim przypadku musisz:

0b00001010 & 0b11110111 = 0b00000010

Gdyby czwarty bit był już ustawiony na zero, nic by się nie zmieniło.

Ogólnie operację resetowania flagi można zapisać w następujący sposób

a & ~(1 << b)

Gdzie a jest liczba, której bit zostanie zresetowany do 0. I b czy pozycja bitu ma zostać wyczyszczona.

Aby otrzymać liczbę, w której wszystkie bity są 1oprócz tego, który ma być równy zero, najpierw przesuwamy pozycje 1b w  lewo, a następnie używamy NOToperatora bitowego do odwrócenia wyniku.

Sprawdzanie flagi

Oprócz ustawienia lub zresetowania określonej flagi czasami wystarczy sprawdzić, czy dana flaga jest ustawiona, czyli czy dany bit jest równy 1. Jest to dość łatwe do zrobienia z bitowym plikiem &.

Załóżmy na przykład, że musisz sprawdzić, czy czwarty bit 1w liczbie jest ustawiony na 0b00001010. Następnie musisz to zrobić:

if ( (0b00001010 & 0b00001000) == 0b00001000 )

Ogólnie operację sprawdzania flagi można zapisać w następujący sposób

(a & (1 << b)) == (1 << b)

Gdzie a jest liczba, której bit jest sprawdzany. I b czy pozycja bitu ma być sprawdzona.

4. Szyfrowanie

Operacja bitowa XORjest często używana przez programistów do prostego szyfrowania. Ogólnie takie szyfrowanie wygląda następująco:

result = number ^ password;

Gdzie number są dane, które chcemy zaszyfrować, password jest to specjalny numer używany jako „hasło” do danych i result jest zaszyfrowanym numerem.

number == (number ^ password) ^ password;

Ważną rzeczą jest to, że XORdwukrotne zastosowanie operatora do liczby daje oryginalny numer, niezależnie od „hasła”.

Aby odzyskać number z programu encrypted result, wystarczy ponownie wykonać operację:

original number = result ^ password;

Przykład:

class Solution
{
   public static int[] encrypt(int[] data, int password)
   {
     int[] result = new int[data.length];
     for (int i = 0; i <  data.length; i++)
       result[i] = data[i] ^ password;
     return result;
   }

   public static void main(String[] args)
   {
     int[] data =  {1, 3, 5, 7, 9, 11};
     int password = 199;

     // Encrypt the array of data
     int[] encrypted = encrypt(data, password);
     System.out.println(Arrays.toString(encrypted));

     // Decrypt the array of data
     int[] decrypted = encrypt(encrypted, password);
     System.out.println(Arrays.toString(decrypted));
   }
}