B reprezentacja danych w pamięci



Pobieranie 495.18 Kb.
Strona1/6
Data08.05.2016
Rozmiar495.18 Kb.
  1   2   3   4   5   6
B

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).1
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 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 1. 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ę:


x

y

x  y

0

0

0

0

1

0

1

0

0

1

1

1

Tabela 2. 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:




x

y

x  y

0

0

0

0

1

1

1

0

1

1

1

1

Tabela 3. 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 4. 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. Symbolizuje go taka zwrócona w obydwie strony strzałka: . Można więc utożsamiać to działanie z równością.




x

y

x  y

0

0

1

0

1

0

1

0

0

1

1

1

Tabela 5. 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 6. Wartości logiczne implikacji
Logicznego wyjaśnienia takiej a nie innej postaci tej tabelki nawet nie będę próbował się podjąć. 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 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ć.



Systemy liczbowe

Odkąd wynaleziono pieniądze i koło, ludzie zaczęli kręcić interesy :) Równie dawno temu ludzie zaczęli liczyć. Policzyć trzeba było nie tylko pieniądze, ale np. upolowane mamuty i inne mniejsze albo większe rzeczy.


Liczby trzeba było jakoś zapisywać. Powstały więc różne sposoby na to. Na co dzień posługujemy się systemem dziesiętnym oraz cyframi arabskimi. Jednak znamy też np. cyfry rzymskie. Także podział na 10, 100 czy 1000 części nie jest wcale tak oczywisty, jak mogłoby się wydawać patrząc na jednostki miar takie, jak kilometr, centymetr czy kilogram. Doba ma przecież 24 godziny, a godzina 60 sekund.
To wszystko są pozostałości po przeszłości, które uświadamiają nam względność naszego sposobu liczenia i możliwość tworzenia nieskończenie wielu różnych, nowych sposobów zapisywania liczb.

Teoria

Poznamy teraz różne systemy liczbowe oraz nauczymy się zapisywać liczby w dowolnym z nich i zamieniać między nimi.

Na początek porcja nieco ciężkostrawnej teorii, którą jednak trzeba jakoś przetrawić :)

Wstęp

Zastanówmy się przez chwilę, w jaki sposób zapisywane są liczby. Dowolnie dużą liczbę jesteśmy w stanie zapisać za pomocą pewnej ilości cyfr, których mamy do dyspozycji dziesięć: 0, 1, 2, 3, 4, 5, 6, 7, 8 i 9. Stąd nazwa naszego systemu – system dziesiętny.


Jednak cyfra cyfrze nierówna. Na przykład w liczbie 123, cyfra 1 ma inne znaczenie niż cyfra 2 czy 3. Ta pierwsza nazwana bywa cyfrą setek, druga – cyfrą dziesiątek, ostatnia zaś – cyfrą jedności.

Skąd te nazwy? Zauważmy, że 1, 10, 100 itd. to kolejne potęgi liczby 10 – która jest podstawą naszego systemu dziesiętnego.


100 = 1

101 = 10

102 = 100

103 = 1000

itd.
System pozycyjny to taki, w którym znaczenie znaków zależy od ich pozycji.
System wagowy to taki, w którym każdej pozycji cyfry przypisana jest inna waga.
Wynika z tego, że nasze używane na co dzień cyfry arabskie w systemie dziesiętnym są systemem pozycyjnym wagowym. Cyfry rzymskie są wyłącznie systemem pozycyjnym, bo poszczególne pozycje cyfr nie mają w nim przypisanych na stałe wag, takich jak 1, 10, 100 itd.
Zostawmy już cyfry rzymskie w spokoju i zajmijmy się normalnymi cyframi arabskimi. Pomyślmy co by było, gdyby do zapisywania liczb używać innej ilości cyfr – np. tylko pięciu? Za ich pomocą także dałoby się zapisać dowolną liczbę. Rodzi się jednak pytanie: jakie byłyby to cyfry?
W systemach o podstawie N mniejszej niż 10 używamy N pierwszych cyfr, tzn. cyfr od 0 do (N-1) włącznie. Np. w systemie siódemkowym używalibyśmy siedmiu cyfr: 0, 1, 2, 3, 4, 5 i 6.

Kiedy zabraknie cyfr, stosuje się kolejne litery alfabetu. Mogą być małe albo duże, ale chyba lepiej wyglądają duże. Np. w systemie trzynastkowym używalibyśmy znaków: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B i C i wszystkie je nazywalibyśmy cyframi.



Wzór

A teraz uwaga, bo będzie straszny wzór ;)

Pokaże nam on, w jaki sposób „zbudowana jest” każda liczba w dowolnym systemie.

m, n  C, m  0, n  0, m  n


L to nasza liczba.

N to podstawa systemu (np. 10 dla systemu dziesiętnego).

m to indeks ostatniej cyfry (tej z prawej strony), albo inaczej mówiąc liczba przeciwna do ilości cyfr po przecinku, np. w liczbie 1984.0415 m=-4.

n to indeks pierwszej cyfry (tej z lewej strony), albo inaczej mówiąc ilość cyfr przed przecinkiem pomniejszona o 1, np. w liczbie 1984.0415 n=3.

Wynika z tego, że pierwsza cyfra przed przecinkiem ma indeks 0, poprzednie cyfry mają kolejne indeksy dodatnie, a cyfry po przecinku mają kolejne indeksy ujemne numerowane w drugą stronę.



i to indeksy kolejnych cyfr.

ai to kolejne cyfry w naszej liczbie.

Przykład

Zanim jednak pokażę przykład, musisz wiedzieć jeszcze jedną ważną rzecz. Otóż musimy nauczyć się oznaczania, w jakim systemie zakodowana (czyli zapisana) jest dana liczba. Inaczej nie wiedzielibyśmy np., czy liczba 320 zapisana jest w systemie czwórkowym, piątkowym czy może dziewiątkowym.

Dlatego wprowadźmy następujące oznaczenie: Przyjmujemy, że system, w jakim zakodowana jest liczba, zapisywali będziemy w indeksie dolnym za nawiasem, w który ujęta jest dana liczba, np. (320)5. Jeśli liczba występuje bez nawiasu i indeksu umawiamy się, że zakodowana jest w naszym normalnym systemie dziesiętnym.
Możemy już przystąpić do przeliczenia liczby z jakiegoś systemu na system dziesiętny. Weźmy liczbę (320)5. Rozwijając ją wg przedstawionego wyżej wzoru mamy:
(320)5 = 3*52 + 2*51 + 0*50 = 3*25 + 2*5 + 0*1 = 75 + 10 + 0 = 85
Okazuje się, że liczba (320)5 zapisana w systemie piątkowym przyjmuje w systemie dziesiętnym postać liczby 85.
Nie mniej ważne od zapisywania jest odpowiednie czytanie liczb. Liczby w systemie innym niż dziesiętny nie wolno czytać tak, jak np. „trzysta dwadzieścia”! Należy mówić zawsze „trzy, dwa, zero”.

Dlaczego? Zauważ, co oznaczają tamte słowa. „Trzysta dwadzieścia” to „trzy setki” i „dwie dziesiątki”. Nieświadomie mówimy więc w ten sposób o cyfrze setek i cyfrze dziesiątek, a te kolejne potęgi dziesiątki są wagami kolejnych cyfr jedynie w systemie dziesiętnym.

Patrząc na powyższy przykład można przy okazji wysnuć wniosek, że w systemie piątkowym mamy do czynienia z „cyfrą dwudziestek piątek”, „cyfrą piątek” i „cyfrą jedności”, a wcześniej zapewne z „cyfrą sto dwudziestek piątek” (bo 53 = 125).
Być może zwróciłeś uwagę na prawidłowość, że do zapisania tej samej liczby w systemie o niższej podstawie (mniejszej ilości dostępnych cyfr) potrzeba więcej cyfr.

Ćwiczenia

Począwszy od tego miejsca zamieszczał będę zadania do samodzielnego wykonania wraz z odpowiedziami w przypisie. Mocno zalecam wykonanie przynajmniej niektórych z nich, ponieważ pozwolą ci one lepiej zrozumieć istotę sprawy oraz wyćwiczyć umiejętności potrzebne do zrozumienia dalszej partii materiału.


Zadanie 12

Rozkoduj do systemu dziesiętnego liczby:



  1. (13)7

  2. (666)7

  3. (666)11

  4. (ABBA.1)13

Praktyka

Jeśli po tych teoretycznych rozważaniach nie bardzo potrafisz wyobrazić sobie to wszystko, nie martw się. Właśnie teraz jest czas i miejsce, by spróbować wyjaśnić systemy liczbowe trochę bardziej „łopatologicznie”.


Wyobraź sobie mechaniczny licznik, np. gazu, prądu, wody, kilometrów lub jakikolwiek inny, który masz w domu albo w samochodzie.


Rysunek 1. Liczba jako mechaniczny licznik z tarczami.
Licznik taki składa się z kilku tarcz, które mogą się obracać. Na ich obwodzie napisane są kolejne cyfry. Granicę między cyfrą ostatnią a pierwszą zaznaczyłem na rysunku niebieską linią (jaki system liczbowy przedstawia rysunek?)3.
Zasada działania licznika jest następująca: Kręcimy za szarą korbkę powodując obracanie się ostatniej tarczy (tej po prawej stronie). Tarcza pokazuje kolejne cyfry. Kiedy dojdzie do ostatniej i zostanie po raz kolejny obrócona, pokazywała będzie z powrotem pierwszą cyfrę (czyli 0). Dodatkowo spowoduje wtedy przekręcenie następnej tarczy o jedną cyfrę do przodu.
Nietrudno wyobrazić sobie co będzie, kiedy ta druga tarcza osiągnie ostatnią cyfrę. Po następnym obróceniu pokaże 0 oraz spowoduje zwiększenie o jedną pozycję tarczy trzeciej. Ogólnie można powiedzieć, że każdy pełny obrót tarczy poprzedniej powoduje na koniec obrócenie tarczy następnej (na lewo od niej) o jedną pozycję.

Dlatego w systemie dziesiętnym po liczbie 9 następuje liczba 10, a po liczbie 99 występuje liczba 100.



Ćwiczenia

Zadanie 24

Wyprowadź tabelkę kilku kolejnych liczb systemu trójkowego począwszy od 0 korzystając z wyobrażenia liczby jako licznika z tarczami.



Kodowanie liczb całkowitych

Potrafimy już rozkodować liczbę zapisaną w dowolnym systemie na system dziesiętny. Pora nauczyć się kodować liczbę dziesiętną w dowolnym innym systemie.


Nie bój się, nie będzie kolejnego strasznego wzoru :) Takie przeliczanie to czysta praktyka i doskonała zabawa. A więc zaczynamy!

Reszta z dzielenia

Do zabawy potrzebny będzie kalkulator oraz przypomnienie pewnego dawno zapomnianego drobiazgu matematycznego. Zanim jeszcze poznaliśmy w szkole podstawowej ułamki, dzielenie liczb wykonywaliśmy „pod kreskę”. Nad liczbą dzieloną zostawał wynik dzielenia, a na dole otrzymywaliśmy coś, co nazywało się resztą.


Właśnie owa reszta z dzielenia jest czymś, co tutaj i w wielu innych zagadnieniach programistycznych zajmuje bardzo ważne miejsce. Przypomnijmy sobie więc, jak to było…
10:3 = 3.3333…, ale równie dobrze 3 i reszty 1
Dlaczego właśnie 1?

Po pierwsze dlatego, że kiedy pomnożymy wynik dzielenia przez dzielnik, iloczyn będzie się różnił od liczby dzielonej właśnie o resztę (3*3 + 1 = 10).

Po drugie, ponieważ w liczbie 10 trójka „mieści się” 3 razy i zostaje jeszcze liczba 1.
Takie dzielenie z obcięciem reszty nazywane bywa dzieleniem całkowitym, a działanie dające w wyniku samą resztę z dzielenia (z pominięciem właściwego ilorazu) – resztą z dzielenia albo modulo.
W C++ do dzielenia całkowitego służy ten sam operator, co do dzielenia liczb rzeczywistych: /. Działa on jako operator dzielenia całkowitego wtedy, kiedy obydwa argumenty działania są typu całkowitego.
Reszta z dzielenia to działanie zdefiniowane tylko dla liczb całkowitych, któremu odpowiada w C++ operator %.

  1   2   3   4   5   6


©absta.pl 2016
wyślij wiadomość

    Strona główna