Megatutorial D.B - Reprezentacja danych w pamięci.pdf - Język C++ - matte1

REPREZENTACJA DANYCH W

PAMIĘCI

Adam Sawicki „Regedit”

sawickiap@poczta.onet.pl

Jest 10 rodzajów ludzi –

- ci, którzy rozumieją kod dwójkowy

i ci, którzy go nie rozumieją.

hakerskie ujęcie socjologii

W tym dodatku mowa będzie o sprawach, które mają miejsce w komputerze praktycznie

na najniższym możliwym poziomie. Będziemy się zajmowali zerami i jedynkami. Poznamy

także sposób, w jaki komputer zapisuje w pamięci wszelkie informacje.

Wbrew temu, co mogłoby się wydawać, wiadomości tego rodzaju nie są bezużyteczne.

Mają one ogromne zastosowanie w praktyce programistycznej. Dlatego radzę podejść do

tej lektury poważnie i postarać się zrozumieć opisane tu, miejscami niestety niełatwe

informacje.

Pamiętaj: Wszystko wydaje się trudne, dopóki nie stanie się proste!

Algebra Boole’a

Wbrew groźnie brzmiącej nazwie, zaczniemy od rzeczy całkiem prostej. Poznamy

podstawowe, teoretyczne zasady operowania na zerach i jedynkach, zwane algebrą

Boole’a lub logiką dwuwartościową.

Boole George (1815-1864), logik i matematyk angielski, od 1849 profesor matematyki

w Queen's College w Cork (Irlandia), członek Towarzystwa Królewskiego (Royal Society)

w Londynie. Zajmował się logiką formalną, rachunkiem prawdopodobieństwa, opracował

algebrę dla zbioru dwuelementowego (algebra Boole'a). Główne dzieło - An Investigation

of The Laws of Thought (1854). 97

Algebra Boole’a posługuje się jedynie dwiema możliwymi cyframi. Przyjęło się zapisywać

je jako 0 i 1. Można też wyobrazić je sobie jako dwa przeciwne stany – prawda (ang.

true ) i fałsz (ang. false ), stan wysoki (ang. high – w skrócie H) i niski (ang. low – w

skrócie L), gruby i chudy, yin i yang czy cokolwiek innego :)

Działania

Na tych dwóch dostępnych liczbach definiuje się kilka podstawowych działań.

Negacja

Jest to działanie jednoargumentowe oznaczane symbolem ~ (tzw. tylda – czyli taki

wężyk pisany nieco u góry :) Bywa też oznaczane przez takie coś: ¬ lub przez pisany za

97 Źródło: http://wiem.onet.pl/

332

negowanym wyrażeniem apostrof: ‘. Możnaby je porównać znanej z normalnej

matematyki zamiany liczby na przeciwną za pomocą poprzedzającego znaku minus -. Tak

jak liczba –5 jest przeciwna, do liczby 5, tak ~x oznacza stan przeciwny do stanu

oznaczonego przez x. Ponieważ w logice dwuwartościowej wartości są tylko… dwie,

nietrudno jest wypisać tabelkę dla tego działania:

x ~x

0 1

1 0

Tabela 13. Wartości logiczne negacji

Jak widać, zanegowanie wartości powoduje jej zamianę na wartość przeciwną, czyli drugą

spośród dwóch możliwych.

Można jeszcze dodać, że negacja nazywana bywa też przeczeniem, a jej słownym

odpowiednikiem jest słowo „nie” (ang. not ). Jeśli głębiej zastanowisz się nad tym,

wszystko okaże się… logiczne! Stan, który nie jest zerem – to jedynka. Stan, który nie

jest jedynką – to zero :D

Koniunkcja

Przed nami kolejne działanie kryjące się pod tajemniczą nazwą. Jest to działanie

dwuargumentowe, które można porównać znanego nam mnożenia. Symbolizuje go taki

oto dziwny znaczek przypominający daszek: ∧ .

Mnożąc jakąkolwiek liczbę przez 0, otrzymujemy 0. Z kolei 1*1 daje w wyniku 1.

Identycznie wynika iloczyn wartości Boole’owskich. Skonstruujmy więc tabelkę:

y x ∧ y

Tabela 14. Wartości logiczne koniunkcji

Koniunkcja bywa też nazywana iloczynem, a odpowiadającym jej słowem jest „i”.

Faktycznie możemy zauważyć, że aby działanie dało w wyniku jedynkę, jedynką muszą

być obydwa argumenty działania: pierwszy i drugi.

Alternatywa

Skoro jest mnożenie, powinno być też dodawanie. Pan Boole o nim nie zapomniał, więc

mamy kolejne działanie. Jego symbol jest przeciwny do symbolu koniunkcji (odwrócony

daszek) i wygląda tak: ∨ .

Tylko dodawanie dwóch zer daje w wyniku zero. Jeśli choć jednym ze składników jest

jedynka, wynikiem dodawania jest liczba większa od zera – 1 albo 2. Ponieważ dwójka w

algebrze Boole’a nie występuje, zamienia się na… nie nie! Nie „zawija się” z powrotem na

zero, ale zostaje jakby „obcięta” do jedynki.

Tabelka będzie więc wyglądała tak:

y x ∨ y

333

Tabela 15. Wartości logiczne alternatywy

Słówkiem odpowiadającym alternatywie jest „lub”. Widzimy, że wynikiem działania jest

1, jeśli wartość 1 ma przynajmniej jeden spośród argumentów działania – pierwszy lub

drugi. A więc wszystko się zgadza.

Różnica symetryczna

Działanie to jest często pomijane w podręcznikach logiki. Tymczasem jego znacznie z

punktu widzenia programisty jest ogromne. Jak bardzo – to okaże się później.

Na razie zajmijmy się jego zdefiniowaniem. Aby sporządzić tabelkę, przyda się angielska

nazwa tej operacji. Brzmi ona exclusive or (w skrócie xor ) – co oznacza „wyłącznie lub”.

Aby w wyniku otrzymać 1, jedynką musi być koniecznie tylko pierwszy lub tylko drugi

argument tego działania, nie żaden ani nie obydwa.

x y x ⊕ y

0 0 0

0 1 1

1 0 1

1 1 0

Tabela 16. Wartości logiczne różnicy symetrycznej

To by było na tyle, jeśli chodzi o operacje logiczne konieczne do wprowadzenia cię w

świat komputerowych bitów. Aby jednak twoja wiedza z dziedziny zwanej logiką (tak,

tak! – na pierwszym roku informatyki jest osobny przedmiot o takiej nazwie, na którym

uczą właśnie tego! :) była pełna, opiszę jeszcze szybciutko pozostałe dwa działania.

Ekwiwalencja

Ekwiwalencja to inaczej równoważność i odpowiada jej nieco przydługie stwierdzenie o

treści: „wtedy i tylko wtedy, gdy”. Daje ono w wyniku jedynkę wtedy i tylko wtedy, gdy

obydwa argumenty są takie same. Można więc utożsamiać to działanie z równością.

Symbolizuje go taka zwrócona w obydwie strony strzałka: ⇔ .

x y x ⇔ y

0 0 1

0 1 0

1 0 0

1 1 1

Tabela 17. Wartości logiczne ekwiwalencji

Implikacja

To zdecydowanie najbardziej zakręcone i najtrudniejsze do zapamiętania działanie

logiczne. Cieszmy się więc, że programista raczej nie musi go pamiętać :)

Inna nazwa implikacji to wynikanie, a odpowiadające mu stwierdzenie brzmi: „jeżeli …, to

…”. Oznaczane jest strzałką skierowaną w prawo: ⇒ . Oto jego tabelka:

x y x ⇒ y

0 0 1

0 1 1

1 0 0

1 1 1

Tabela 18. Wartości logiczne implikacji

334

Logicznego wyjaśnienia takiej a nie innej postaci tej tabelki nawet nie będę próbował się

podjąć 98 . Przejdźmy teraz lepiej do dalszej części logiki, by jak najszybciej mieć ją już za

sobą :)

Aksjomaty

Poznamy teraz kilka prostych wzorów, które ukażą nam podstawowe zależności pomiędzy

poznanymi działaniami logicznymi.

Przemienność

a ∨ b = b ∨ a

Dodawanie też jest przemienne – jak w matematyce.

a ∧ b = b ∧ a

Mnożenie też jest przemienne.

Łączność

(a ∨ b) ∨ c = a ∨ (b ∨ c)

Dodawanie jest łączne – jak w matematyce.

(a ∧ b) ∧ c = a ∧ (b ∧ c)

Mnożenie też jest łączne.

Rozdzielność

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)

Mnożenie jest rozdzielne względem dodawania.

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Dodawanie też jest rozdzielne względem mnożenia – a w normalnej matematyce nie!!!

Identyczność

a ∨ 0 = a

a ∨ 1 = 1

a ∧ 0 = 0

a ∧ 1 = a

To wynika bezpośrednio z tabelek.

Dopełnienie

a ∨ ~a = 1

a ∧ ~a = 0

Bo jeden z argumentów zawsze będzie przeciwny do drugiego.

Prawa De Morgana

~(a ∨ b) = ~a ∧ ~b

~(a ∧ b) = ~a ∨ ~b

Logika w programowaniu

Uff… Pora wrócić do sedna sprawy, czyli do programowania. Tutaj często zachodzi

potrzeba reprezentowania jednego z dwóch stanów. Przykładowo zmienna Blad w stanie

98 Może niesłusznie, gdyż wyjaśnienie jest dość proste. Implikacja ilustruje wynikanie jednych faktów z drugich,

a takie rozumowanie jest słuszne zawsze, z wyjątkiem sytuacji, gdy ze stwierdzenia prawidziwego

wyprowadzamy stwierdzenie fałszywe. Odpowiada to trzeciemu wierszowi tabelki. [przypis: Xion]

335

1 oznaczałaby fakt wystąpienia błędu, a w stanie 0 fakt jego niewystąpnienia – czyli że

wszystko jest w porządku.

Typ logiczny

Typem danych w C++ reprezentującym wartości logiczne jest bool . Dwa stany

reprezentowane są zaś przez specjalne słowa kluczowe – true oraz false . Można też

używać identyfikatorów TRUE i FALSE pisanych dużymi literami.

Dla przykładu weźmy linijkę kodu, który tworzy wspomnianą zmienną i wstępnie ją

inicjalizuje:

bool Blad = false ;

Wyrażenia logiczne

Oprócz bezpośrednich wartości true oraz false , wartości typu bool zwracane są także

przez operatory porównania takie, jak == (równy), != (różny), < (mniejszy), >= (większy

lub równy) itp.

Każda okazja jest dobra, aby po raz kolejny przestrzec przez typowym błędem, na który

(niestety?) w całej swej zachwalanej przez wielu elastyczności pozwala język C++.

Chodzi o różnicę pomiędzy operatorem przypisania = , a operatorem porównania

(równości) == . Ten pierwszy także zostanie zawsze zaakceptowany w miejscu drugiego,

ale z pewnością spowoduje inny (czyli nieprawidłowy) efekt.

Uważaj na to!

Wartość innego typu – np. liczba – także może zostać potraktowana jako wartość

logiczna. Przyjęte zostanie wówczas 0 (fałsz), jeśli wartość jest zerowa (np. liczbą jest 0)

oraz prawda w każdym innym wypadku.

Ta cecha języka C++ jest całkiem przydatna, ponieważ pozwala sprawdzać „niezerowość”

zmiennych (szczególnie wskaźników) bez posługiwania się operatorem porównania, np.:

if (Zmienna)

std::cout<< "Zmienna jest niezerowa" ;

Operatory logiczne

Poznane na początku działania algebry Boole’a mają, jak można się domyślać, swoje

odpowiedniki w języku programowania. W C++ są to symbole odpowiednio:

¾ ! – negacja – przeczenie – „nie” (jednoargumentowy)

¾ && - koniunkcja - iloczyn - „i” (dwuargumentowy)

¾ || - alternatywa – suma – „lub” (dwuargumentowy)

Najłatwiej zrozumieć istotę działania tych operatorów zapamiętując ich słowne

odpowiedniki (te w cudzysłowach). Rozważmy przykład:

int Liczba = 7 ;

void * Wskaznik = 0 ;

bool Wartosc = ( !(Wskaznik) || (Liczba == 6) ) && false ;

Wskaznik jest zerowy, a więc jego wartością logiczną jest false . Po zanegowaniu

zmienia się w true . Zmienna Liczba nie jest równa 6, a więc wartością porównania

będzie false . true lub false daje true , true i false daje w końcu false . Zmienna

Wartosc zostanie więc ostatecznie zainicjalizowana wartością false .

Postaraj się przeanalizować to jeszcze raz, dokładnie, i w pełni wszystko zrozumieć.

Megatutorial D.B - Reprezentacja danych w pamięci.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: