[C++] Operatory bitowe

opublikował: Razi91, 2014-03-04

Przy omawianiu typu logicznego bool lub instrukcji warunkowej z pewnością była mowa o łączeniu warunków operatorami logicznymi: AND (&&), OR (||), XOR(^^), NOT(!). Ich zadaniem było tworzenie logicznych zdań. Wynikiem operacji logicznej zawsze jest wartość logiczna (true lub false). Jeśli argumentami takiej operacji były liczby, były rzutowane do wartości logicznej: jeśli była równa 0 – false, dowolna inna – true.

W pamięci jednak nawet jednobitowa informacja taka jak wartość logiczna zajmuje cały bajt.

Operatory bitowe

Operatory bitowe to operacje logiczne na całych blokach (liczbach) bitów (wartości logicznych). Aby je zrozumieć, należy najpierw przyjrzeć się systemowi binarnemu.

Operatory bitowe mają swoje odpowiedniki w operatorach logicznych: AND(&), OR (|), XOR(^), NOT(~). W skrócie jest to wykonanie operacji logicznych na wszystkich odpowiadających sobie bitach podanych liczb:

Suma:

0101 (5) |
0011 (3) =
0111 (7)

Iloczyn:

0101 (5) &
0011 (3) =
0001 (1)

Alternatywa wykluczająca:

0101 (5) ^
0011 (3) =
0110 (6)

Negacja

0101 (5) ~ =
1010 (10)

 

 

Analogia jest łatwa do zauważenia : operacja logiczna na każdej parze bitów z osobna. Z początku operatory te mogą wydać się zupełnie niepotrzebne, o ich zastosowaniu później.

Operatory przeniesienia

Inną grupą operacji bitowych są przeniesienia. Operatory te przesuwają „treść” binarną całej liczby w lewo lub prawo o n bitów. W C++ i innych językach zapisuje się je operatorami << oraz >>. Przykład:

0010 0101 (37) << 1 = 0100 1010 (74)
0010 0101 (37) << 2 = 1001 0100 (148)
0010 0101 (37) >> 2 = 0000 1001 (9)

Łatwo się domyślić że przeniesienie w lewo to mnożenie o 2^n (37*2²=148), w prawo: dzielenie (37/2²=9,25=9).

Operator przesunięcia jest wygodnym sposobem na uzyskanie „jedynki” na konkretnym bicie bez rozpisywania całej liczby binarnie lub szesnastkowo: 1<<n: jedynka na (n+1)tym bicie:
1<<0 == 0001 (2) = 1
1<<1 == 0010 (2) = 2
1<<2 == 0100 (2) = 4
1<<3 == 1000 (2) = 8

Przesunięcia muszą uwzględniać takie przypadki jak liczby ujemne oraz utrata wartości bitów (tak jak w 3 przykładzie), dlatego wyróżnia się 3 rodzaje przesunięć:
logiczne: za nowy bit (przy przesunięciu w lewo: pojawiający się po prawej) zawsze podstawia się 0, wychodzący jest zapominany (1111>>1 = 0111, 1111<<1 = 1110)
obrót: wychodzący bit idzie na drugi koniec (0011>>1 = 1001)
arytmetyczne:  zachowywany jest znak, czyli pierwszy bit (bit znaku) w kodzie U2 (1101>>1 = 1110, 0111>>1 = 0011, 1111<<1 = 1110)

Ciekawostka

Dzielenie jest najkosztowniejszą operacją dla procesora. Kompilatory unikają je jak tylko się da, dlatego gdziekolwiek pojawia się dzielenie (lub mnożenie, które również jest kosztowne) przez stałe 2 (lub jego potęgę) zamienia je na właśnie operacje przesunięcia.

Zastosowanie

Najlepszym przykładem zastosowania operatorów bitowych jest używanie ich do sprawdzania flag. 32-bitowy integer to 32 bity informacji na 4 bajtach, 32 informacje logiczne które zapisane z użyciem typu bool zajmowałyby całe 32 bajty.

Flaga to inaczej liczba z jedną jedynką (lub więcej) opisująca jakąś cechę. Wartości flag nie powinny się pokrywać, chyba że się nie wykluczają – wspólna (pod)cecha.
W systemach Uniksowych podstawowe prawa dostępu do plików zapisane są w formie 9-bitowego ciągu reprezentowanego trzema cyframi w systemie ósemkowym. Działanie tego systemu można zobaczyć na stronie http://www.chmod.pl/. Mając 9-bitowe prawa plików szybko i łatwo można sprawdzić czy ten plik ma ustawione praw do zapisu przez grupę: jest to 5 bit, zatem flaga tej cechy wynosi 000010000. Jeśli plik będzie miał prawa 111110100 wystarczy wykonać operację AND i sprawdzić czy wynik jest różny od zera – jeśli jest, to znaczy że ten bit miał wartość 1 i prawo zostało udzielone.

Maską zwykło nazywać się grupę bitów spełniającą pewne zadanie. Może to być grupa (suma bitowa) flag danej kategorii.

Operacje na flagach

Przy założeniu że v to sprawdzana wartość, f to flaga, a F to maska (przy niektórych) zawierająca tą flagę

  • Dodaj flagę: v = v | f
  • Operator sumy logicznej ustawia kolejne bity na 1, reszty nie modyfikuje, nawet jeśli flagi były ustawione (w przypadku sumy arytmetycznej wystąpiłoby przeniesienie), jest zatem bezpieczny
  • Odejmij flagę: v = v & (!f)
  • Przypisze do wartości wartość przefiltrowaną o wartość flagi: 1101 & !(0100) = 1101 & 1011 = 1001.
  • Czy flaga ustawiona? v & f == f
  • Iloczyn bitowy wyciągnie z wartości tylko bity należące do flagi, operator porównania sprawdzi czy wynik całkowicie pokrywa się z flagą. Jeśli flaga była jednobitowa, nie trzeba porównywać z samą flagą, wystarczy że wynik jest różny od zera
  • Czy flaga NIE jest ustawiona? v & f != f
  • Jeśli iloczyn wartości i flagi nie jest równy fladze, to znaczy że flaga ta nie została ustawiona. Jeśli flaga miała wiele bitów, wynik może nie być równy, ale też nierówny 0
  • Czy jakaś flaga należąca do maski jest ustawiona? v & F !=0
  • Jeśli mamy maskę F poskładaną z wielu flag, możemy sprawdzić czy któraś z nich jest ustawiona
  • Czy jest ustawiona jakaś alternatywa? v & (f^F) != 0
  • Jeśli jest jakaś flaga uogólniająca F (maska poskładana z kilku flag) można sprawdzić czy jest ustawiona któraś z alternatyw, ale nie ta konkretna.
  • Czy tylko ta flaga jest ustawiona? v == f
  • Najzwyklejsze porównanie

Przykład zastosowania flag

Szachy


Pole może mieć stany: puste, gracz biały, gracz czarny + rodzaj figury. Może być zatem opisane flagami (od najmłodszego bitu):

  • [0] gracz biały
  • [1] gracz czarny
  • [4-6] figura

W takim ustawieniu logicznym by było że pole o wartości 0 byłoby polem pustym, wartość pozostałych bitów jest bez znaczenia. Wartość 1 na pierwszym, najmłodszym bicie sugeruje że pole jest zajęte przez gracza zdefiniowanego przez drugi bit: 0 – biały, 1 – czarny. Aby te pole miało sens, musi być pierwszy bit ustawiony na 1. Następne 3 bity dają miejsce na opisanie jednej z 8 figur (w szachach mamy ich 6, trzeba na to jednak poświęcić 3 bity). Flagi zatem wyglądają następująco:

    const char WHITE = 0x01; // 0000 0001
    const char BLACK = 0x02; // 0000 0010
    const char NOT_EMPTY= WHITE | BLACK; // 0000 0011
    const char KING = NOT_EMPTY | 0x10; // 0001 0000
    const char ROOK = NOT_EMPTY | 0x20; // 0010 0000
    const char BISHOP = NOT_EMPTY | 0x30; // 0011 0000
    const char QUEEN = NOT_EMPTY | 0x40; // 0100 0000
    const char KNIGHT = NOT_EMPTY | 0x50;  // 0101 0000
    const char PAWN = NOT_EMPTY | 0x60; // 0110 0000
    const char FIGURE = KING | ROOK | BISHOP | QUEEN | KNIGHT | PAWN; // 0111 0000

Mamy tutaj dwie złożone flagi, określane również jako maski: NOT_EMPTY – określa czy którykolwiek z graczy znajduje się na danym polu oraz FIGURE – maska pokrywająca wszystkie bity używane przez figury. Trzeba tu zaznaczyć, że warunek v&f==f dla maski niekoniecznie musi mieć możliwość spełnienia (tu akurat nie ma takiej możliwości), tutaj mamy do czynienia ze „stanami zabronionymi”, konkretnie wystąpienie takiej sytuacji jak field[x][y]&NOT_EMPTY==NOT_EMPTY jest błędem, bo by oznaczało że na danym polu znajdują się figury obu graczy (co nie jest możliwe).

W drugim przypadku przeznaczamy 3 bity na wyliczanie. 3 bity dają 8 możliwości, wykorzystujemy jedynie 6, pozostają 2 niewykorzystane. Ich wystąpienie również oznacza błąd. W tym przypadku nie wykorzystałem samych 0, dzięki czemu

A teraz do rzeczy. Co nam taki układ da? Plansze można zorganizować w tablicy charów:

   char field[8][8];

Gracz może poruszać się tylko swoimi pionkami. Dzięki użyciu flag można łatwo sprawdzić czy pole należy do gracza w celu wyznaczenia dostępnych pól:

    if (field[x][y] & player)

Następnym krokiem jest sprawdzenie rodzaju figury:

    switch(field[x][y] & FIGURE){
    case KING: //dla króla
    case ROOK: //dla wieży
    case BISHOP: //dla gońca
    case QUEEN: //dla hetmana
    case KNIGHT: //dla skoczka
    case PAWN: //dla pionka
    }

W każdym z tych przypadków można uaktualnić najstarszy bit każdego pola zezwalający na ruch (pole te może posłużyć przy rysowaniu zasięgu figury):

    if (reachable) field[x][y] |= REACHABLE;
    else field[x][y] &= ~REACHABLE;

Figurę można postawić na pustym polu:

    if (field[x][y] == 0)

lub na figurze przeciwnika, można to rozwiązać „na piechotę”:

    if (player==WHITE && field[x][y]&BLACK==BLACK ||
player==BLACK && field[x][y]&WHITE==WHITE)// gracz biały, a na polu czarny...

albo krócej:

    if (field[x][y] & ~player & NOT_EMPTY) //na polu nie jest gracz, ale nie jest puste

Po skończonym ruchu (i obsłudze ewentualnego zbicia figury przeciwnika) wystarczy zamienić wartości:
    field[nx][ny] = field[x][y];
    field[x][y] = 0;

Zamianę piona na figurę można przeprowadzić nie sprawdzając nawet z którym graczem mamy do czynienia:

    field[x][y] = (field[x][y] & ~FIGURE) | choosedFigure;

Plansza do gry w szachy została zatem zmieszczona w 64 bajtach, taka oszczędność może przy dzisiejszych maszynach wydawać się niepotrzebna, ale ten przykład dobrze obrazuje oszczędność jaką można uzyskać. Normalnie do opisu potrzebowalibyśmy zmiennych:
który gracz: biały, czarny, żaden
która figura

Pola bitowe?

Język C++ oferuje coś takiego jak pola bitowe. W skrócie są to pola w strukturze które zajmują określoną ilość bitów umożliwiając w ten sposób użycie jednego bajtu pamięci przez kilka zmiennych. Powyższą strukturę można by zapisać tak:

struct Pole{
    int gracz:2;
    int _u:2 //pole nieużywane, wypełnia tylko miejsce aby struktura była zgodna z flagami
    int figura:3;
}

Ta struktura w pamięci zajmie 1 bajt mimo obecności dwóch intów i jedneg bool’a (2+3+1 = 5 – tyle bitów, wymagane wyrównanie do pełnego bajtu). Wtedy pole `gracz’ może przyjąć wartości 0 – brak gracza, 1 – gracz biały, 2 – gracz czarny, podobnie z figurami. Sprawdzenie czy pole jest zajęte sprowadziłoby się do sprawdzenia czy pole `gracz’ jest większe od 0.

Nie jest to jednak w żaden sposób wydajniejsze od stosowania flag. Na etapie kompilacji odwołania do tych pól sprowadzi się do iloczynu oraz przeniesienia bitowego. Wyciągnięcie pola `figura’ jest równoznaczne z szeregiem operacji:

    data[x][y]&FIGURE>>4

Natomiast ustawienie figury:

    data[x][y] = (data[x][y]&~FIGURE) | PAWN

Jest tu zatem niepotrzebna operacja przeniesienia bitowego. Optymalizator może jednak wpaść na pomysł że jest ono zbędne i wykona odwrotną operację na stałej wpisanej przez programistę w kodzie w czasie kompilacji.

Stosowanie flag ma jednak nad polami bitowymi taką przewagę, że flagi można łatwo łączyć operatorem sumy bitowej. Biały król to WHITE|KING, warunek w kodzie

    if(data[x][y]==WHITE|KING)

Wzorzec budowniczego

Wzorzec ten polega na stworzeniu kreatora obiektów którego konstrukcja wymaga podania wielu często opcjonalnych danych. Może się zdarzyć, że pewne ustawienia muszą być ustawione, albo gdy coś zostało ustawione, coś innego powinno również być ustawione. Tworzymy wtedy dla każdego ustawienia osobną flagę, przykład czysto abstrakcyjny:

    const int F1=1;
    const int F2=F1<<1;
    const int F3=F2<<1;
    const int F4=F3<<1;
    const int M1=F1|F2;
    const int M2=F3|F4;
    int set=0;

Następnie przy każdym ustawieniu dodajemy flagę do `set’:

    void setF1(int data){
        set |= F1;
        //instrukcje
    }

A we właściwej metodzie budującej:

    Obj* build(){
        if( !(set&M1==M1) || set&M2==M2) )  //jeśli para M1 lub M2 nie została ustawiona
            return null; //błąd, zwróć null’a
        if(!set&F4) //jeśli F4 nie jest ustawiony
            setF4(defaultF4); //ustaw jakiś domyślny
        //budowanie i zwracanie obiektu
    }

Ustawienie domyślnego F4 mogłoby być niepżądane w przypadku gdyby programista sam go ustawił. Flagi pozwalają w łatwy i optymalny dla pamięci sposób przechowywać takie informacje.

Podsumowanie

Operatory bitowe są wykorzystywane między innymi przy organizacji pamięci i zoptymalizowania jej zużycia. Opierają się jak sama nazwa wskazuje na logice, zapewniając podstawowe cztery operacje logiczne: iloczyn, sumę, alternatywę oraz negację, a także przesunięcia bitowe. Stosuje się je nie tylko w C++, ale także i innych językach.

<table style="\\\\\\\\\\\\\\\\&quot;width:" 460px;="" height:="" 100px;\\\\\\\\\\\\\\\\"="" cellpadding="\\\\\\\\\\\\\\\\&quot;1\\\\\\\\\\\\\\\\&quot;" cellspacing="\\\\\\\\\\\\\\\\&quot;1\\\\\\\\\\\\\\\\&quot;" border="\\\\\\\\\\\\\\\\&quot;1\\\\\\\\\\\\\\\\&quot;">

       

 


Zarejestruj się albo zaloguj aby dodać komentarz


Brak komentarzy.
wszystkie oferty

 

 

 

 
 
 

Kalendarz wydarzeń

WSZYSTKIE WYDARZENIA