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 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.
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)
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.
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.
Przy założeniu że v to sprawdzana wartość, f to flaga, a F to maska (przy niektórych) zawierająca tą flagę
Pole może mieć stany: puste, gracz biały, gracz czarny + rodzaj figury. Może być zatem opisane flagami (od najmłodszego bitu):
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
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 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.
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="\\\\\\\\\\\\\\\\"width:" 460px;="" height:="" 100px;\\\\\\\\\\\\\\\\"="" cellpadding="\\\\\\\\\\\\\\\\"1\\\\\\\\\\\\\\\\"" cellspacing="\\\\\\\\\\\\\\\\"1\\\\\\\\\\\\\\\\"" border="\\\\\\\\\\\\\\\\"1\\\\\\\\\\\\\\\\"">