Megatutorial D.C - Manipulacje bitami.pdf - Język C++ - matte1

MANIPULACJE BITAMI

Karol Kuczmarski „Xion”

karol.kuczmarski@gmail.com

Lepiej uczyć się rzeczy zbytecznych niż

żadnych.

Seneka

Od czasu sławetnego stwierdzenia, że 640 kB będzie po wsze czasy wystarczającą ilością

pamięci, minęło już ponad ćwierć wieku. W informatyce taki okres to już całe eony – nic

dziwnego więc, że dzisiaj operujemy już pojemnościami będącymi nie tylko tysiąc, ale

nawet kilkanaście czy kilkaset tysięcy razy większymi od tej „ostatecznej”. Cóż,

proroctwa rzadko się sprawdzają :)

Wobec takich ogromnych ilości pojedynczy bit – jak wiemy, najmniejsza jednostka

informacji – może wydawać się nieskończenie mały i przez to zupełnie nieznaczący. Co

mianowicie możemy zapisać przy pomocy pojedynczego bitu lub ich grupki – bajtu,

słowa?… Okazuje się, że całkiem sporo.

Manipulacje pojedynczymi bitami czy zespołami wciąż są bowiem przydatną

umiejętnością. Wśród ich zastosowań można wymienić tak ważne zagadnienia jak:

¾ odczyt i zapis plików w formatach binarnych

¾ implementacja protokołów wielu popularnych aplikacji sieciowych

¾ współpraca programu z większością bibliotek programistycznych

W tym dodatku przedstawiam zatem pewne techniki operowania na tych niewielkich

porcjach informacji – bitach i ich ciągach, czyli słowach . Na początku więc przyjrzymy

się podstawowym działaniom na ciągach bitów, jakie oferuje większość języków

programowania (w tym oczywiście C++). Następnie spróbujemy przy ich pomocy

skontruować procedury pozwalające na dostęp do dowolnego zakresu bitów w słowie;

dzięki temu nabierzesz wprawy w opisywanych tu operacjach. Wreszcie przyjrzymy się

pewnym prawdziwym zastosowaniom takiej zabawy, przede wszystkich technice flag

bitowych . Na koniec zerkniemy jeszcze na kilka przydatnych „sztuczek” realizowanych

przy pomocy opisanych wcześniej operacji.

Temat jako taki wydaje się więc bardzo niskopoziomowy, lecz wcale nie oznacza to, że

musi on być trudny. Prawdopodobnie jest on po prostu zbyt często pomijany, a bez jego

znajomości nawet wyedukowany programista może być bezradny wobec kodu

zawierającego instrukcje manipulacji bitami. Celem tego dodatku jest zatem uchronienie

cię przed takimi sytuacjami :)

Operacje bitowe

Rozpoczniemy od dość wnikliwego rzutu oka na najważniejsze elementarne operacje

bitowe, z jakich zwykle się korzysta. Naturalnie, zależy nam szczególnie na tych, które

występują w C++ w postaci operatorów, choć pod tym względem wszystkie

najważniejsze języki programowania są do siebie bardzo podobne.

Wśród tych najprostszych działań wyróżnimy sobie dwa typy: funkcje logiczne oraz

przesunięcia bitowe.

Funkcje logiczne

Przypomnijmy, co w ogóle rozumiemy pod pojęciem pojedynczego bitu . Zazwyczaj mówi

się, że jest to najmniejsza jednostka informacji, mogąca przyjmować tylko jeden z dwóch

stanów: 0 lub 1. Zero w tej sytuacji utożsamiamy z logicznym fałszem, a jedynkę – z

prawdą. Taka konwencja pozwala nam stosować do bitów spójniki znane z logiki, na

przykład koniunkcję czy alternatywę. Możemy więc określić, ile wynosi 0 ∧ 1, 1 ∨ 1, itd.

Ale to nie jeszcze nie wszystko. Zastosowanie funkcji logicznych wobec pojedynczych

bitów pozwala nam także powiedzieć, jak dana funkcja działa dla ciągów bitów (słów

bitowych). Oznacza to po prostu zastosowanie jej do kolejnych bitów, np.:

1 0 0 1 0 1 1 0

∧ 1 0 1 0 1 1 0 1

= 1 0 0 0 0 1 0 0

Tabela 1. Koniunkcja dwóch ciągów bitów

Głównie na takich właśnie ciągach działają operatory bitowe w C++ i innych jezykach

programowania. Reprezentują one rzecz jasna pewne funkcje logiczne, którym

przyjrzymy się po kolei 1 .

Bardzo podobny przegląd jest częścia Dodatku B, Reprezentacja danych w pamięci . Tutaj

jednak skoncentrujemy się raczej na tym, jak omawiane funkcje pozwalają nam zmieniać

wartości bitów zamiast na ich znaczeniu w logice.

Negacja

Prawdopodobnie najprostszą funkcją jest negacja (czyli zaprzeczenie), gdyż jest ona

operacją jednoargumentową. Dla danego bitu wynikiem jest bit do niego przeciwny – a

zatem jedynka zmienia się w zero, zaś w zero w jedynkę. Dla ciągu bitów jest to więc

analogicznie zamiana wszystkich zer w jedynki i wszystkich jedynek w zera.

Negację oznacza się na wiele sposobów: tyldą (~) lub znakiem ¬ przed negowanym

wyrażeniem, a także apostrofem ‘ za nim. Czasami też można spotkać poziomą kreską

nad argumentem. Naturalnie we wszystkich przypadkach funkcja działa tak samo :) A

ponieważ programujemy w C++, będziemy tu używali symbolu operatora negacji z tego

języka, czyli ~.

b ~b

0 1

1 0

Tabela 2. Tabelka prawdy dla działania negacji bitowej

Negacja zmienia zatem wartość bitu na przeciwną. Zastosowanie jej dwa razy powinno

nam więc dać wyjściową wartość – jest to prawo podwójnego zaprzeczenia ,

prezentujące się następująco:

~~b = b

Jak zobaczymy, działanie negacji będzie dla nas szczególnie przydatne w połączeniu z

przesunięciami bitowymi. W sumie jednak trudno mówić o zastosowaniach tej operacji –

po prostu stosujemy ją tam, gdzie jest konieczna :D

1 W tym podrozdziale literką b będę oznaczał dowolny bit.

Suma

Pozostałe interesująca nas funkcje są już dwuargumentowe. Jedną z nich jest

alternatywa ( suma ), którą można interpretować jako pewnego rodzaju dodawanie.

Zastrzeżenie ‘pewnego rodzaju’ jest całkiem na miejscu, jako że zaraz poznamy inny

sposób dodawania bitów.

Logicznym oznaczeniem alternatywy jest ∨ , ale w przypadku działań na bitach częściej

używamy symbolu | - odpowiada on rzecz jasna operatorowi z C++ i języków o podobnej

składni. Czasem używamy też słowa or (‘lub’) ze względu na spójnik logiczny, jakiemu

odpowiada alternatywa.

Jak zatem działa alternatywa tudzież suma bitowa? Dla dwóch bitów wynikiem jest zero

tylko wtedy , gdy oba bity są zerami. W przypadku, gdy któryś z nich jest jedynką,

rezultatem zawsze będzie jeden. W szczególności będzie tak również wtedy, kiedy

zarówno pierwszy jak i drugi bit są jedynkami – wynikiem też będzie jeden. Właśnie to

odróżnia alternatywę od opisanego dalej drugiego sposobu dodawania bitów.

Dla ciągów bitów opisana operacja ta jest oczywiście wykonywana dla każdej

odpowiadającej sobie pary, zaś wynik jest złożeniem tych wszystkich rezultatów.

Nie zaszkodzi jeszcze podkreślić, że działanie sumy jest przemienne – niezależnie od

kolejności argumentów wynik będzie więc taki sam.

a b a | b

0 0 0

0 1 1

1 1 1

1 0 1

Tabela 3. Tabelka wyników działania sumy bitowej

Wymienone wyżej własności pozwalają nam w łatwy sposób ustawiać stan bitów na 1. Z

powyższego opisu wynika bowiem, iż:

b | 1 = 1

b | 0 = b

Te dwie tożsamości będą nam bardzo pomocne w dostępie do wybranego zakresu bitów

w słowie.

Iloczyn

Drugim działaniem jest iloczyn , zwany też koniunkcją . W kontekście wartości bitów

interpretujemy go jako mnożenie – działa bowiem tak, jak „normalny” iloczyn liczb 0 i 1.

Jako operator logiczny koniunkcja jest natomiast równoważna spójnikowi ‘i’ (ang. and ),

oznaczanemu przez ∧ . W C++ jako odpowiedni operator bitowy dla iloczynu używany jest

symbol & .

Przewidywanie wyników zastosowania tego działania nie jest trudne, gdy wiemy, że pełni

ono rolę iloczynu. Istotnie, dla dwóch bitów wynikiem jest jedynka wyłącznie wówczas ,

gdy oba bity są jedynkami. W innym przypadku, kiedy którykolwiek bit jest zerem (a

zwłaszcza oba), rezultatem też będzie zero. Jest to w sumie dość oczywiste –

pomnożenie czegokolwiek przez zero powinno dać właśnie zero. Bity nie są tu żadnym

wyjątkiem :)

a b a & b

0 0 0

0 1 0

1 1 1

a b a & b

1 0 0

Tabela 4. Tabelka wyników działania iloczynu bitowego

Podobnie jak suma, iloczyn jest przydatnym narzędziem do modyfikacji wartości bitów.

Zauważmy mianowicie, że wobec powyższych własności mamy:

b & 0 = 0

b & 1 = b

Iloczyn pozwala zatem zerować stan wybranych bitów, nie ruszając innych. Niedługo

zobaczymy to w praktyce.

Suma modulo 2

Dwa bity możemy dodać w jeszcze jeden sposób. Przedstawiona na początku zwykła

suma tak naprawdę bowiem nie jest wcale ich „normalnym” sposobem dodawania. W

przypadku sumowania dwóch jedynek wynikiem arytmetycznym byłoby oczywiście 2

(binarnie 10). Przyjęcie w tym przypadku rezultatu 1 zapewnia nam jednak zgodność z

logicznym pojęciem alternatywy oraz – jak widzieliśmy – jest przydatne do ustawiania

bitów.

Jednak możemy przecież ustalić sumę dwóch jedynek na 0 i ma to więcej sensu niż się

może początkowo wydawać. Zachowujemy bowiem cyfrę z „prawdziwego”

arytmetycznego wyniku, a jedynie ignorujemy tzw. przeniesienie (ang. carry ) na

następny bit. W ten sposób powstaje działanie sumy modulo 2 , zwanej tej różnicą

symetryczną . W logice istnieje mniej znane, acz równoważne działanie alternatywy

wykluczającej. Nie ma ono jakiegoś oczywistego spójnika w języku naturalnym 2 , jak

również matematycznego symbolu – używa się zwykle ⊕ lub ∨ .

W języku angielskim spotyka się za to często słówko xor , od eXclusive OR – ‘alternatywa

wykluczająca’. Pod tym względem nie zawodzi nas także język C++, gdzie działanie

bitowej sumy modulo 2 ma swój operator ^ .

Jak zatem funkcjonuje to działanie? Różni się ono od poprzedniej sumy tylko na jednym

miejscu, lecz łatwiej je zapamiętać przy pomocy innej własności. Otóż różnica

symetryczna dwóch bitów daje jedynkę tylko wtedy , gdy bity te są różne . Dla

równych bitów wynikiem działania sumy modulo 2 jest zawsze zero.

Jeszcze inaczej możemy to interpretować przy pomocy pojęcia reszty z dzielenia – stąd

zresztą operacja ta bierze jedną ze swoich nazw. Mianowicie, suma modulo 2 jest

właśnie… sumą modulo 2 :), tzn. zwykłym (arytmetycznym) dodaniem wartości dwóch

bitów i wyciągnięcia z wyniku reszty z dzielenia przez 2:

⊕

( ) 2

mod

a b a ⊕ b

0 0 0

0 1 1

1 1 0

1 0 1

Tabela 5. Tabelka wyników działania sumy modulo 2

2 Niekiedy podawany jest spójnik albo (w znaczeniu „albo, albo”).

Możesz się zastanawiać – do czego mogłoby nam się przydać takie dziwne działanie?

Prawdopodobnie nie widać tego na pierwszy rzut oka, ale stosują się do niego takie oto

dwie tożsamości (w razie czego można to sprawdzić :D):

b ^ 0 = b

b ^ 1 = ~b

Operacja sumy modulo 2 pozwala zatem przeprowadzać negację wybranych bitów przy

jednoczesnym zachowaniu wartości pozostałych.

Pozostałe funkcje dwuargumentowe

W dalszych przykładach będziemy korzystali niemal wyłącznie z powyższych trzech

operacji dwuargumentowych (i jednej jednoargumentowej). Nie zaszkodzi jednak

przyjrzeć się także innym, a nawet… wszystkim :)

NAND i NOR

Istnieją dwie ciekawe dwuargumentowe funkcje logiczne, które nie są tak znane jak

przytoczone wyżej, a pewnym sensie są „równie dobre” jak one. Te dwie funkcje są

oznaczane najczęściej swoimi angielskimi nazwami NAND i NOR – od Negative AND i

Negative OR .

Określenia te wskazują, że rzeczone funkcje są związane z operacjami sumy oraz ilocznu,

a ponadto w grę wchodzi jeszcze negacja. Faktycznie, są to po prostu zanegowane

operacje and i or :

nand(x, y) = ~(x & y)

nor(x, y) = ~(x | y)

Specjalność tych dwóch formuł polega na tym, że teoretycznie używając tylko i

wyłącznie jednej z nich można zapisać wszystkie funkcje logiczne działające na

dowolnie wielu argumentach. Dlaczego tak jest? Wiemy rzecz jasna, że jest to możliwe

przy korzystaniu z oddzielnej operacji negacji oraz zwykłej sumy i iloczynu. Otóż okazuje

się, że te „normalne” działania można uzyskać posługując się tylko NANDem lub tylko

NORem:

~x = nand(x, x) = nor(x, x)

x | y = nand(nand(x, x), nand(y, y)) = nor(nor(x, y), nor(x, y))

x & y = nand(nand(x, y), nand(x, y)) = nor(nor(x, x), nor(x, x))

Nie wydaje się to szczególnie efektowne (ani efektywne), jako że suma i iloczyn

wymagają zastosowania swych zanegowanych odpowiedników aż trzykrotnie. Okazuje się

jednak, że ta nieefektywność może być pozorna. W układach elektronicznych

składających się z bramek logicznych (czyli części symulujących działanie omawianych

tutaj funkcji) zastosowanie NAND i NOR daje często lepsze rezultaty niż bramek

odpowiadających „zwykłym” funkcjom logicznym negacji, sumy i iloczynu. Zarówno koszt

układu, jak i jego opóźnienia – mimo zwiększonej ogólnej liczby bramek – są wtedy

bowiem mniejsze.

Wszystkie funkcje logiczne

Poznaliśmy więc już pięć dwuargumentowych operacji logicznych. Skoro tak dobrze nam

idzie, to może zapytajmy od razu: ile jest ich w sumie? Okazuje się, że nie jest to wcale

trudne pytanie. Możemy odpowiedzieć nawet na ogólniejsze; otóż:

Istnieje dokładnie

2 funkcji logicznych biorących n argumentów i zwracających jeden

rezultat.

Megatutorial D.C - Manipulacje bitami.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: