« poprzedni punkt 

5. Operacje na bitach

Liczby całkowite (typów byte, short, int, long) są reprezentowane w pamięci komputera w postaci binarnej jako ciągi bitów. Bit, który znajduje się w takim zapisie najbardziej z lewej strony nazywa się bitem najstarszym (najbardziej znaczącym), a ten najbardziej z prawej - najmłodszym (najmniej znaczącym).
Najstarszy bit jest tzw. bitem znaku - jeśli jest ustawiony (ma wartość 1) to liczba jest ujemna, a jeśli nie (ma wartość 0) - to liczba jest dodatnia.

r

Jak pamiętamy z wykładu 1 - dziesiętną wartość liczby zapisaną w systemie dwójkowym możemy uzyskać sumując kolejne iloczyny wartości bitów (1 lub 0) i odpowiednich potęg 2. Uwzględnienie liczb ujemnych wymaga, by wartość bitu znaku "brana była" z minusem. Dlatego na powyższym rysunku:
7 = -0*27 + 0*26 + 0*25 + 0*24 +0*23 + 1*22 + 1*21 + 1*20
-7 = -1*27 + 1*26 + 1*25 + 1*24 +1*23 + 0*22 + 0*21 + 1*20


Taki zapis liczb całkowitych nazywa się zapisem z uzupełnieniem do dwóch


Łatwo dostrzec, że z tego powodu wartość bezwzględna największej całkowitej liczby ujemnej jest zawsze większa od wartości bezwględnej największej całkowitej liczby dodatniej. W przypadku wartości typu byte najmniejsza możliwa wartość równa jest 100000000, czyli -1*27 = - 128, natomiast największa możliwa licznba dodatnia równa jest 01111111 = 127.


Pamiętamy też, że wartości typu char (reprezentujące znaki) mogą być traktowane jak liczby całkowite. W tym przypadku jednak najstarszy bit nie jest traktowany jako bit znaku - zatem wartości typu char (zajmujące 2 bajty) mogą kształtować się w przedziale od 0 do 65536.

Na bitach wartości wszystkich całkowitych typów numerycznych (w tym bitach wartości typu  char) możemy wykonywać operacje.
Do operowania na bitach liczb całkowitych służą następujące operatory:

  • jednoargumentowy operator uzupełnienia jedynkowego ~ ,
  • dwuargumentowe operatory przesunięcia bitowego >> (w prawo) i << (w lewo) oraz operator przesunięcia bitowego w prawo bez propagacji bitu znakowego (>>>),
  • dwuragumentowy operator koniunkcji bitowej &,
  • dwuargumentowy operator bitowej różnicy symetrycznej ^ (wykluczające ALBO),
  • dwuargumentowy operator alternatywy bitowej | .

Każdy z argumentów wszystkich wymienionych operatorów bitowych musi być typu całkowitego.
Operatory przesunięcia bitowego powodują przesunięcie bitów swojego lewego argumentu o liczbę pozycji specyfikowaną przez prawy argument w lewo (operator <<), lub w prawo (operator >>). Przy przesuwaniu w lewo, młodsze (zwalniane) bity zapełniane są zerami; przy przesunięciu w prawo zwalniane bity zapełniane są wartością bitu znakowego (najstarszego). co nazywa się propagację bitu znakowego. W przypadku użycia operatora >>> taka propagacja nie występuje i niezależnie od wartości bitu znaku zwalniane bity są zapełniane zerami.

Rozpatrzmy przykłady:

byte b = 1; -> bitowa reprezentacja: 00000001 (1)
b << 1 -> 00000010 (2)
b << 4 -> 00010000 (16)

A zatem w przypadku, gdy a jest którąś z potęg dwójki, kolejne przesunięcie w lewo mnoży wartość a przez 2. A co się stanie gdy będziemy chcieli przesunąć w lewo bity największej z możliwych liczb danego typu?
Warto wiedzieć, że lewy argument operatora << (jeśli był typu byte, short lub char) jest promowany do typu int i całe wyrażenie ma wartość typu int (jeśli argument był typu long - wartość wyrażenia jest typu long).
Zatem taki program:

public class Test {

  public static void main(String[] args) {
    byte b = Byte.MAX_VALUE;
    System.out.println(b + " " + (b << 1));
    System.out.println(b + " " + (byte) (b << 1));
    int i = Integer.MAX_VALUE;
    System.out.println(i + " " + (i << 1));
  }

}

wyprowadzi:
127 254
127 -2
2147483647 -2

Pierwszy wynik jest faktycznie rezultatem mnożenia wartości b przez dwa tylko dlatego, że nastąpiła promocja wartości b do typu int i typem wyniku wyrażenia b << 1 jest int.
Trzeci wynik pokazuje, że przesunięcie bitów może doprowadzić do zmiany bitu znaku z 0 na 1. W tym przypadku nie było miejsca na promocję (czyli faktycznie zwiększenie liczby bitów zajmowanych przez liczbę) w konsekwencji bit znaku stał się 1 i otrzymaliśmy liczbę ujemną.
Pośredni, drugi wynik uwidacznia dokładnie to samo. Dokonaliśmy tu konwersji do typu byte, zatem rezultat jest taki jakbyśmy operowali na wartościach typu byte (bez promocji):

127 = 01111111

a po przesunięciu bitów o jedno miejsce, otrzymujemy:

11111110

co jest równe dokładnie -2.

Zobaczmy jak działa operator >> (przesunięcie bitów w prawo - z propagacją znaku)

byte b = 127; -> 01111111
b >> 1 -> 00111111 (63)
b >> 2 -> 00011111 (31)
b >> 3 -> 00001111 (15)

Operacja a >> n dla liczb całkowitych jest równoważna całkowitoliczbowemu dzieleniu (dającemu w rezultacie całkowitą część rezultatu dzielenia) a/2n.

Dla liczb ujemnych wygląda to w następujący sposób:
byte b = -64; -> 11000000
b >> 1 -> 11100000 (-32)
b >> 2 -> 11110000 (-16)
b >> 3 -> 11111000 (-8)
c >> 4 -> 11111100 (-4)

(zwalniane bity są zapełniane wartością bitu znakowego tj. 1)
Zauważmy więc, że jeśli b = -1 (11111111), to przesunięcie bitów w prawo da wynik -1.

Logiczne operatory bitowe ( ~,^, &, |) służą do ustalania wartości bitów rezultatu za pomocą wartości bitów argumentów. Operator uzupełnienia jedynkowego ~ zamienia w swoim jedynym argumencie wszystkie zerowe bity na 1, a 1 na 0. Sposób w jaki określane są bity rezultatu pozostałych logicznych operacji bitowych obrazuje poniższa tablica, w której a1 i a2 oznaczają argumenty operatorów bitowych.

Wartość bitu
w a1
Wart. odpo-
wiadajęcego
mu bitu w a2
Wart. odpowiadającego bitu rezultatu oper.
a1 & a2
a1 ^ a2
a1 | a2
00000
10011
01011
11101

Np. jeśli a1 = 5, a2 = 7, to logiczne operacje bitowe są przeprowadzane w następujący sposób:

a1 & a2 = ...0101
        & ...0111
         ---------
          ...0101 = 5
a1 ^ a2 = ...0101
        ^ ...0111
         ---------
          ...0010 = 2
a1 | a2 = ...0101
        | ...0111
        ---------
          ...0111 = 7

Zwróćmy uwagę, że operacje te dotyczą tylko najmłodszych 3 bitów, niezależnie od tego jakiego są typu i ile miejsca w pamięci zajmują argumenty a1 i a2.
Np. aby wyzerować najmłodszy bit całkowitej zmiennej x - niezależnie od jej typu  możemy napisać:

x = x & ~0x1; 

zerowe bity stałej 0x1 staną się 1, a jedyny bit o wartości 1 - zerem; w rezultacie w x zerowany będzie najmłodszy bit - niezależnie od tego jakiego typu jest i ile miejsca zajmuje x.

Operacje bitowe są właśnie najbardziej przydatne do ustawiania i testowania wartości bitów. Często w programowaniu wykorzystuje się tzw. flagi - znaczniki, których wartości określają np. charakterystyki jakiegoś zdarzenia, albo jaki jest stan jakiegoś obiektu. Flagi mają zwykle charakter zero-jedynkowy - szkoda więc byłoby na każdą z nich tracić 8 bitów, gdy wystarczy 1. Zestawy flag zapisujemy więc zwykle jako bity wartości jakiejś zmiennej - typu byte (8 flag), albo int (32 flagi), albo long (64 flagi). Za pomocą operatorów bitowych możemy sprawdzać które z flag przechowywanych w tych zmiennych są ustawione i modyfikować ich ustawienie.

Popatrzmy na następujący przykładowy program (wykorzystamy w nim statyczną metodę getBits(wart) z klasy Unspec, która zwraca tablicę znaków 0 - 1, pokazujących bitową reprezentację przekazanej jako argument wartości; klasę tę za chwilę zbudujemy i omówimy).

public class Flags {

  public static void main(String[] args) {

    final int  FL1 = 0x01,    // stałe pokazujące które bity (flagi) mają
               FL2 = 0x02,    // być testowane lub ustawiane
               FL3 = 0x04,
               FL4 = 0x08;

    int flags = 0;
    flags = flags | FL1;                   // ustawia flagę 1 (najmłodszy bit)
    show("flags = flags | FL1",
          flags);
    flags = 0;
    flags =  flags | FL3;                  // ustawia flagę 3 (trzeci bit)
    show("flags = flags | FL3",
          flags);
    flags = 0;
    flags = flags | (FL1 | FL4);           // ustawia 1 i 4 flagę
    show("flags = flags | (FL1 | FL4)",
          flags);

   // czy flaga 1 ustawiona
   if ((flags & FL1) > 0) System.out.println("Flaga 1 ustawiona");
   else System.out.println("Flaga 1 NIE ustawiona");

   // czy flaga 2 ustawiona
   if ((flags & FL2) > 0) System.out.println("Flaga 2 ustawiona");
   else System.out.println("Flaga 2 NIE ustawiona");

   // czy flagi 1 i 4 ustawione (jednoczesnie)
   int mask = FL1 | FL4;
   if ((flags  &  mask) ==  mask) System.out.println("Flagi 1 i 4 ustawione");
   else System.out.println("Flagi 1 i 4 NIE ustawione");

   // czy flagi 1 i 2 ustawione (jednoczesnie)
   mask = FL1 | FL2;
   if ((flags & mask) == mask) System.out.println("Flagi 1 i 2 ustawione");
   else System.out.println("Flagi 1 i 2 NIE ustawione");

  }

  static void show(String s, int flags) {
    System.out.println(s);
    char[] bits =  Unspec.getBits(flags);
    System.out.println(new String(bits) + "   --- val: " + flags);
  }

}

Program wyprowadzi następujące informacje:

flags = flags | FL1
00000000000000000000000000000001   --- val: 1
flags = flags | FL3
00000000000000000000000000000100   --- val: 4
flags = flags | (FL1 | FL4)
00000000000000000000000000001001   --- val: 9
Flaga 1 ustawiona
Flaga 2 NIE ustawiona
Flagi 1 i 4 ustawione
Flagi 1 i 2 NIE ustawione

Proszę przeanalizować działanie programu i przetestować inne ustawienia flag.

Znając już działanie operatorów bitowych możemy pokusić się o stworzenie klasy Unspec, która dostarczy następujących statycznych metod, zwracających w tablic bitowe reprezentacje wartości różnych typów:

public static char[]  getBits(byte)
public static char[]  getBits(char)
public static char[]  getBits(int)
public static char[]  getBits(long)


Przed lekturą dalszego tekstu proszę to zadanie rozwiązać samodzielnie


Możliwe rozwiązanie:

public class Unspec {

  public static char[] getBits(byte v)  {
    return getBits(8, (long) v);
  }

  public static char[] getBits(char v)  {
    return getBits(16, (long) v);
  }


  public static char[] getBits(int v)  {
    return getBits(32, (long) v);
  }


  public static char[] getBits(long v)  {
    return getBits(64, v);
  }

  private static char[] getBits(int n, long v)  {
    char[] bits = new char[n];
    long mask = 1;
    for (int k = n-1; k >= 0; k--) {
      if ((v & mask) != 0) bits[k] = '1';
      else bits[k] = '0';
      mask =  mask << 1;
    }
    return bits;
  }
}

oraz program testujący, w którym - jako argumenty wywołania podajemy kolejno liczbę typu long, liczbę typu int, znak, liczbę typu byte:

class Test {
  public static void main(String[] args) {
    long l = Long.parseLong(args[0]);
    int i  = Integer.parseInt(args[1]);
    char c = args[2].charAt(0);
    byte b = Byte.parseByte(args[3]);
    System.out.println("Wartość typu long " + l);
    System.out.println(new String(getBits(l)));
    l = Long.MAX_VALUE;
    System.out.println("Maksymalna wartość typu long " + l);
    System.out.println(new String(getBits(l)));
    l = Long.MIN_VALUE;
    System.out.println("Minimalna wartość typu long " + l);
    System.out.println(new String(getBits(l)));
    System.out.println("Wartość typu int " + i);
    System.out.println(new String(getBits(i)));
    System.out.println("Wartość typu char: znak " + "'" + c + "'" + ", kod " + (int) c);
    System.out.println(new String(getBits(c)));
    System.out.println("Wartość typu byte " + b);
    System.out.println(new String(getBits(b)));
  }
}

Program ten - przy podanych argumentach: 1 -1 a -7 wyprowadzi:

Wartość typu long 1
0000000000000000000000000000000000000000000000000000000000000001
Maksymalna wartość typu long 9223372036854775807
0111111111111111111111111111111111111111111111111111111111111111
Minimalna wartość typu long -9223372036854775808
1000000000000000000000000000000000000000000000000000000000000000
Wartość typu int -1
11111111111111111111111111111111
Wartość typu char: znak 'a', kod 97
0000000001100001
Wartość typu byte -7
11111001


« poprzedni punkt