Wpisany przez Tomasz Lubiński,
01 października 2008 17:42
Poniżej zdefiniujemy operacje bitowe oraz przykłady ich zastosowania podczas programowania.
- Operacja bitowa "i" (ang. bitwise and)
Jest to operacja dwuargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
a and b
a & b
Wynikowy bit jest ustawiany na 1 tylko wówczas gdy obydwa bity argumentów ustawione są na 1. Możemy zatem powiedzieć, że wynikiem jest 1 gdy bit a i bit b są ustawione na 1. Tabela wyników dla tego działania jest następująca:
a AND b b=0 b=1 a=0 0 0 a=1 0 1 Przykład:
0101 and 1100 = 0100 - Operacja bitowa "lub" (ang. bitwise or)
Jest to operacja dwuargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
a or b
a | b
Wynikowy bit jest ustawiany na 1 tylko wówczas gdy przynajmniej jeden bit, któregoś z argumentów ustawiony jest na 1. Możemy zatem powiedzieć, że wynikiem jest 1 gdy bit a lub bit b jest ustawiony na 1. Tabela wyników dla tego działania jest następująca:
a OR b b=0 b=1 a=0 0 1 a=1 1 1 Przykład:
0101 or 1100 = 1101 - Operacja bitowa "albo" (ang. bitwise xor)
Jest to operacja dwuargumentowa, zwana też alternatywą wykluczającą. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
a xor b
a ^ b
Wynikowy bit jest ustawiany na 1 tylko wówczas gdy dokładnie jeden bit, któregoś z argumentów ustawiony jest na 1. Możemy zatem powiedzieć, że wynikiem jest 1 gdy bit a albo bit b jest ustawiony na 1. Tabela wyników dla tego działania jest następująca:
a XOR b b=0 b=1 a=0 0 1 a=1 1 0 Przykład:
0101 xor 1100 = 1001 - Zaprzeczenie bitowe, dopełnienie bitowe (ang. bitwise not, complement)
Jest to operacja jednoargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
not a
~ b
Wynikowy bit jest ustawiany na 1 tylko wówczas gdy bit argumentu jest ustawiony na 0. Możemy zatem powiedzieć, że wynikiem jest 1 gdy bit a nie jest ustawiony na 1. Tabela wyników dla tego działania jest następująca:
a NOT a 0 1 1 0 Przykład:
not 0101 = 1010 - Przesunięcie bitowe w lewo (ang. shift left)
Jest to operacja dwuargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
a shl b
a << b
Operacja polega na przesunięciu a o b bitów w lewo. Przy czym bity pojawiające się z prawej strony (uzupełniające przesunięcie) są ustawiane na 0. Operacja ta jest równoważna mnożeniu przez 2. Przesunięcie o 1 bit to przemnożenie a przez 2, przesunięcie o 2 bity to dwukrotne pomnożenie a przez 2, itd.
Przykład:
0101 shl 3 = 0101000 - Przesunięcie bitowe w prawo (ang. shift right)
Jest to operacja dwuargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
a shr b
a >> b
Operacja polega na przesunięciu a o b bitów w prawo. Operacja ta jest równoważna dzieleniu całkowitemu przez 2. Przesunięcie o 1 bit to podzielenie a przez 2, przesunięcie o 2 bity to dwukrotne podzielenie a przez 2, itd.
Przykład:
010110 shr 3 = 010
- Operacje na pojedynczym bicie
Załóżmy, że mamy dany rejestr, w którym poszczególne bity odpowiadają za włączanie i wyłączanie poszczególnych funkcjonalności. Chcemy w prosty sposób operować na pojedynczym bicie nie zmieniając stanu pozostałych. W tym celu zdefiniujemy sobie bit, który będzie reprezentował bit, na którym dokonujemy operacji. Wszystkie jego bity ustawione są na zero, z wyjątkiem bitu na którym będziemy operować. Operacje zdefiniujemy następująco:
- włączenie bitu: rejestr = rejestr or bit
- wyłączenie bitu: rejestr = rejestr and not(bit)
- przełączenie bitu w stan przeciwny: rejestr = rejestr xor bit
Przykład:
Niech bit = 0100
Włączenie bitu dla rejestr = 1001: 1001 or 0100 = 1101
Wyłączenie bitu dla rejestr = 1101: 1101 and not(0100) = 1101 and 1011 = 1001
Przełączenie bitu dla rejestr = 1001: 1001 xor 0100 = 1101
Przełączenie bitu dla rejestr = 1101: 1101 xor 0100 = 1001 - Maskowanie
Jest to operacja wybierania z większej liczby bitów tylko, tych, które faktycznie nas interesują. W tym przypadku posłużymy się operacją i. Maska będzie wybierać nam, które bity przy porównaniu są dla nas ważne (ustawione w masce na 1). Wówczas jeżeli chcemy porównać dwie dane: dane_1 oraz dane_2 użyjemy następującej konstrukcji:
if dane_1 and maska = dane_2 and maska then...
Doskonałym przykładem są tutaj sieci komputerowe i sposób ich adresacji. W protokole IP wyróżniamy część adresu mówiącą o sieci, w której znajduje się dany komputer, oraz część adresu mówiącą o numerze komputera w danej sieci. By zdecydować czy dany pakiet przesłać dalej czy znajduje się on w naszej sieci musimy sprawdzić czy cześć adresu, w której zawarty jest adres sieci jest zgodny z naszą siecią. Wykonuje się to za pomocą operacji and na adresie sieci oraz masce sieci. Zatem taka decyzja wygląda wówczas następująco:
if adres_pakietu and maska_sieci = adres_moj and maska_sieci then...
Przykład:
Załóżmy, że:
adres_pakietu=11000000101010110000000100100101
adres_moj=11000000101010110001000000010111
maska_sieci=11111111111111110000000000000000
Sprawdźmy czy dany pakiet adresowany jest do naszej sieci:
adres_pakietu and maska_sieci = adres_moj and maska_sieci
11000000101010110000000100100101 and 11111111111111110000000000000000 = 11000000101010110001000000010111 and 11111111111111110000000000000000
11000000101010110000000000000000 = 11000000101010110000000000000000
Równość jest spełniona zatem ten pakiet adresowany jest do naszej sieci. - Upakowywanie danych
Czasem zachodzi potrzeba użycia danych o niestandardowym rozmiarze. Na przykład chcemy zapisywać bardzo wiele razy liczbę, której wartość mieści się w zakresie 0-3. Do zapisania takiego zakresu wystarczą nam dwa bity. Najmniejsza jednostka jaką możemy zapisać na dyku to bajt, który ma 8 bitów. Dlatego też, 4 takie dwubitowe wartości możemy upakować jednym bajcie. Zapis takich upakowanych wartości możemy zapisać następująco:- odczyt upakowanej danej:
odpakowana = (upakowana and maska) shr start_bit - zapis upakowanej danej będzie przebiegał dwuetapowo, najpierw wyczyszczenie miejsca na daną, a następnie jej zapis:
upakowana = upakowana and not(maska)
upakowana = upakowana or (odpakowana shl start_bit)
Maska wskazuje nam miejsce gdzie należy upakować dane, natomiast start_bit jest numerem bitu (licząc od 0 od prawej), pod którym zaczyna się dana.
Przykład:
Załóżmy, że mam 4 wartości: 01 11 10 01 wpisać do jednego bajta.
Kolejne maski dla tych danych zdefiniujemy następująco: 00000011, 00001100, 00110000, 11000000.
Kolejne bity startowe dla tych danych zdefiniujemy następująco: 0, 2, 4, 6.
Zapiszmy zatem drugą wartość do zmiennej bajt = 01101010, miejsce, gdzie zostanie zapisana dana pogrubiono. A więc najpierw czyszczenie miejsca pod nasze dane:
bajt = bajt and not(maska) = 01101010 and not(00001100) = 01101010 and 11110011 = 01100010.
Teraz zapiszemy dane:
bajt = bajt or (dane shl start_bit) = 01100010 or (11 shl 2) = 01100010 or 1100 = 01101110.
Spróbujmy teraz odczytać te dane: dane = (bajt and maska) shr start_bit) = (01101110 and 00001100) shr 2 = 00001100 shr 2 = 11. - odczyt upakowanej danej:
Poprawiony: 03 października 2019 06:52
przełknąłem tą pigułkę w mgnieniu oka i nie żałuję :)