Architektura Komputera  Kodowanie Liczb
KODOWANIE LICZB
WST
P
Współczesne komputery przetwarzają informację w postaci bitów, czyli symboli o dwóch podstawowych postaciach, które oznaczamy
zwykle cyframi 0 i 1 (stąd pochodzi nazwa systemów zerojedynkowych). Nazwę bit wymyślił w czasie drugiego śniadania John Turkey w
roku 1947. Słowo to pochodzi od liter angielskich wyrażeń binary (dwójkowy) oraz digit (cyfra), oznacza więc cyfrę dwójkową. John
rozważał jeszcze dwie inne nazwy - binit oraz bigit, lecz, jak już wiemy, nie przyjęły się one i mamy obecnie bit.
Bity są bardzo wygodne. Poniżej zebraliśmy kilka najważniejszych powodów ich popularności:
" bit ma tylko dwa stany, 0 i 1, dzięki czemu w prosty sposób można konstruować układy elektroniczne, które
przetwarzają bity.
" łącząc bity w grupy można otrzymywać dowolną liczbę symboli złożonych, w których jednak wciąż występują
podstawowe elementy o prostej postaci - bity. Ta własność umożliwia kodowanie dowolnie skomplikowanych
informacji w postaci ciągu bitów.
" dwójkowy system zapisu liczb może być bezpośrednio przeniesiony na bity, co
umożliwia kodowanie dowolnych liczb - dzięki temu komputery mogą wykonywać
najbardziej skomplikowane obliczenia.
" operacje arytmetyczne w systemie dwójkowym są bardzo proste, więc również
stosunkowo proste są układy liczące zrealizowane na bazie tego systemu
" dla bitów można zastosować bezpośrednio reguły algebry Boole'a, co umożliwia
przeprowadzanie dowolnych operacji logicznych.
" w trakcie transmisji bitów, są one bardzo odporne na zakłócenia, więc system ten
sprzyja tworzeniu sieci komputerowych.
Pierwszy na świecie
mikroprocesor Intel 4004
1
Architektura Komputera  Kodowanie Liczb
JEDNOSTKI INFORMACJI
Podstawową jednostką informacji jest bit. To fakt ogólnie znany, jednak trudniej odpowiedzieć na pytanie, co właściwie oznacza to
stwierdzenie. W jaki sposób bity można powiązać z informacją.
Informacja jest tworem czysto abstrakcyjnym. Nie istnieje materialnie. Nie można jej dotknąć, poczuć, zobaczyć. Informację da się
natomiast wyrażać za pomocą symboli, znaków, kodu. Człowiek najczęściej używa słów, pisma, gestów do przekazywania informacji. Ta
sama informacja (idea) może przybierać formę symboli, które, chociaż różne, oznaczają to samo pojęcie. Np. człowiek, human (ang.),
Mensch (niem.), el hombre (hisz.), il uomo (wł.) - w każdym języku symbol (słowo) jest inne, lecz ich wspólną cechę stanowi to samo
znaczenie, czyli właśnie informacja. Skoro do wyrażania informacji możemy używać różnych symboli (słów), to dlaczego nie zastosować
do tego celu bitów? Należy tylko pokazać sposób, jak to zrobić. I tym właśnie się zajmiemy.
Bit
Bit jest symbolem, który może przyjmować dwie różne postacie. Jeśli chcemy zapisać go na papierze, to
stosujemy symbole pomocnicze 0 i 1. Technicznie bit realizowany jest za pomocą dwóch różnych sygnałów.
W technice cyfrowej określa się poziomy napięć, które odpowiadają bezpośrednio dwóm postaciom bitu:
0,4 ... 0,8 V - stan 0 (oznaczany również L - Low - Niski)
2,0 ... 2,4 V - stan 1 (oznaczany również H - High - Wysoki)
Taśma dziurkowana.
Tak kiedyś zapisywano dane.
Każda dziurka odpowiadała
bitowi o stanie 1. Brak dziurki
oznaczał stan 0.
2
Architektura Komputera  Kodowanie Liczb
Układy elektroniczne komputera reagują na te napięcia i w ten sposób przetwarzają bity. Zamiast napięć mogą to być również prądy o
różnych natężeniach lub zwrotach, sygnały o dwóch rozróżnialnych częstotliwościach oraz wiele innych ciekawych sposobów, których
opisanie zajęłoby nam co najmniej kilka lat ciężkiej pracy. Poprzestańmy więc na stwierdzeniu, iż bit to sygnał dwustanowy - jeden stan
oznaczamy jako 0, a drugi jako 1.
Każdy ze stanów bitu może przenosić jedną wiadomość w identyczny sposób, jak np. słówko "stół" przenosi wiadomość na temat rzeczy
z płaskim blatem i zwykle czterema nogami. Tyle tylko, iż słowa naszego języka mają ustalone od stuleci znaczenia, bity natomiast
możemy przystosowywać do dowolnych wiadomości w miarę potrzeb. Jeden bit pozwoli w ten sposób przekazać jedną z dwóch
wiadomości.
Czujnik ruchu.
W razie wykrycia ruchu
w okolicy przekazuje bit
o stanie 1.
3
Architektura Komputera  Kodowanie Liczb
Przykład
Pojedyncze bity używane są do komunikacji z prostymi czujnikami, które reagują na określoną sytuację - np. gaz w chronionym
pomieszczeniu, wzrost temperatury ponad wartość dopuszczalną, osiągnięcie przez ciecz w naczyniu określonego poziomu, otwarcie
drzwi, przerwanie wiązki światła, itp.
Bit informacyjny z czujnika przekazywany jest do centrali na różne sposoby - przewodem elektrycznym, linią światłowodową, torem
radiowym, itp. Ważne jest tylko to, iż w każdym z tych kanałów transmisyjnych wolno pojawić się tylko jednemu z dwóch stanów bitu -
stanowi 0 (np. niskie napięcie, brak prądu, sygnał radiowy o małej amplitudzie itp.) lub stanowi 1 (np. wysokie napięcie, prąd w
przewodzie, sygnał radiowy o dużej amplitudzie itp.).
Jeśli wiemy jak reaguje dany czujnik na określone zdarzenie (co oznaczają stany 0 i 1 przekazywane przez ten czujnik), to w prosty
sposób możemy zinterpretować przekazywaną przezeń informację. Np. otrzymujemy sygnał o stanie 0 i wiemy, że oznacza on, iż czujnik
nic nie wykrył. Jeśli teraz otrzymamy sygnał o stanie 1, oznaczający wystąpienie sytuacji, na którą reaguje dany czujnik, to od razu
możemy to odpowiednio zinterpretować - np. wysłać ekipę strażacką do chronionego czujnikiem pomieszczenia lub włączyć samoczynną
instalację przeciwpożarową. Możliwości jest bez liku, a wszystko za sprawą jednego bitu informacji.
ZAPAMI
TAJ
1 bit może przekazać informację o dwóch różnych zdarzeniach.
Bit oznaczamy małą literką b.
4
Architektura Komputera  Kodowanie Liczb
Grupa bitów
Aparat cyfrowy
Zapamiętuje obraz
jako długi ciąg bitów
Świat jest zbyt skomplikowany, aby zawrzeć go w dwóch wiadomościach. Dlatego bardzo prędko dojdziemy do sytuacji, gdzie należy operować
kilkoma różnymi wiadomościami i bit stanie się niewystarczający. Na szczęście bity możemy łączyć w grupy i traktować je wspólnie jako symbol
złożony. Przy takim podejściu otrzymujemy nieograniczone możliwości tworzenia słów binarnych i przypisywania im znaczeń.Grupa dwóch bitów
oddaje nam do dyspozycji cztery różne symbole, które powstają z kombinacji stanów tworzących je bitów:
00 - symbol pierwszy
01 - symbol drugi
10 - symbol trzeci
11 - symbol czwarty
Każdemu symbolowi możemy przypisać informację o osobnym zdarzeniu. Grupa dwóch bitów może więc przekazać informację o
czterech różnych zdarzeniach.
5
Architektura Komputera  Kodowanie Liczb
PrzykładZałóżmy, iż chcemy zakodować binarnie obrazek pokazany poniżej: Jest on złożony z różnokolorowych punktów, które
nazywamy pikselami (z języka ang. picture element - element obrazu, punkt).
Od razu zauważamy, że punkty są tylko w czterech kolorach. Układamy tablicę kodową kolorów, w której każdemu kolorowi punktu
przyporządkujemy jeden symbol dwubitowy:
- 00
- 01
- 10
- 11
Powiązaliśmy w ten sposób informację z reprezentującymi ją symbolami. Teraz wystarczy już tylko każdy piksel zastąpić symbolem
dwubitowym. W tej postaci obrazek może być przechowywany w pamięci komputera, przesyłany przez sieci teleinformatyczne oraz
przetwarzany.
00 00 00 00 00 00 00 00 0000000000000000
00 00 11 11 11 11 00 00 0000111111110000
00 11 11 11 11 11 00 00 0011111111110000
00 00 11 11 11 11 11 00 0000111111111100
00 00 00 11 11 00 00 00 0000001111000000
00 00 00 00 10 00 00 00 0000000010000000
00 00 00 00 10 00 00 00 0000000010000000
01 01 01 01 01 01 01 01 0101010101010101
6
Architektura Komputera  Kodowanie Liczb
Zwróćmy uwagę na małą czytelność dla ludzi informacji zapisanej w systemie binarnym. Szczególnie, jeśli wszystkie bity zapiszemy w
jednym ciągu:
0000000000000000000011111111000000111111111100000000111111111100000000111100000000000000100000000101010101010101
Należy jednak pamiętać o tym, iż system ten jest przeznaczony dla maszyn, które nie nudzą się i nie męczą.
Dwa bity dają nam cztery symbole. Jeśli zwiększymy liczbę bitów w grupie do trzech, to dostępna ilość symboli wzrośnie do ośmiu:
000 - symbol pierwszy
001 - symbol drugi
010 - symbol trzeci
011 - symbol czwarty
100 - symbol piąty
101 - symbol szósty
110 - symbol siódmy
111 - symbol ósmy
Wynika z tego, iż zwiększenie liczby bitów w grupie zwiększa dwukrotnie liczbę dostępnych symboli binarnych, które mogą przenosić
informację o zdarzeniu. W poniższej tabeli dokonaliśmy odpowiednich obliczeń dla grup bitowych o długościach od 1 do 32 bitów.
7
Architektura Komputera  Kodowanie Liczb
liczba bitów liczba symboli liczba bitów liczba symboli
1 2 17 131072
2 4 18 262144
3 8 19 524288
4 16 20 1048576
5 32 21 2097152
6 64 22 2097152
7 128 23 8388608
8 256 24 16777216
9 512 25 33554432
10 1024 26 67108864
11 2048 27 134217728
12 4096 28 268435456
13 8192 29 536870912
14 16384 30 1073741824
15 32768 31 2147483648
16 65536 32 4294967296
8
Architektura Komputera  Kodowanie Liczb
Liczba symboli wzrasta geometrycznie. Ogólnie dla grupy n bitowej liczba możliwych do wykorzystania symboli binarnych wyraża się
liczbą 2n. Dla każdej skończonej liczby wiadomości zawsze możemy dobrać taką liczbę bitów, aby liczba słówek bitowych była równa lub
większa od liczby wiadomości. Dla n wiadomości wystarczy, aby liczba bitów była równa części całkowitej wyrażenia
(log2(n - 1) + 1).
ZAPAMI
TAJ
n bitów daje 2n symboli
n symboli wymaga [log2(n - 1) + 1] bitów
Przykład
Drukarka komputerowa.
Dane do druku przekazywane
są w postaci ciągu bitów.
Zaprojektować kod binarny przeznaczony do kodowania małych liter alfabetu łacińskiego.
9
Architektura Komputera  Kodowanie Liczb
W tym przypadku wiadomościami będą literki. W alfabecie łacińskim jest ich 26: abcdefghijklmnopqrstuvwxyz. Każda literka musi
być kodowana innym symbolem binarnym. Musimy określić zatem niezbędną liczbę bitów tworzących te symbole. W tym celu
wykorzystujemy drugi z podanych wzorów i otrzymujemy:
[log2(26 - 1) + 1] = [log225 + 1] = [4,64 + 1] = [5,64] = 5 bitów
5 bitów tworzy 32 symbole. Nam potrzebne jest 26, więc 6 symboli nie zostanie wykorzystanych. Od przybytku głowa nie boli. Ważne
jest, aby symboli nie było mniej niż liczba wiadomości do zakodowania. Więcej w niczym nam nie przeszkadza - nawet lepiej, gdyż w
przyszłości będzie można do takiego systemu dodać 6 nowych znaków (n. spacja, przecinek, kropka itp.).
W następnym kroku układamy tabelkę kodu znakowego, w której każdej literce przydzielamy jeden symbol binarny. Po tej operacji
można literki przedstawiać jako symbole binarne oraz z symboli binarnych odczytywać literki. Odwzorowanie jest zatem obustronne.
Binarny kod znakowy
Znak Kod Znak Kod Znak Kod Znak Kod
a 00000 h 00111 o 01110 v 10101
b 00001 i 01000 p 01111 w 10110
c 00010 j 01001 q 10000 x 10111
d 00011 k 01010 r 10001 y 11000
e 00100 l 01011 s 10010 z 11001
f 00101 m 01100 t 10011
g 00110 n 01101 u 10100
10
Architektura Komputera  Kodowanie Liczb
Zamieńmy na bity wg opracowanego schematu słowo "sowa":
s - 10010
o - 01110
w - 10110
a - 00000
Po połączeniu bitów w jeden ciąg otrzymujemy ostatecznie:
10010011101011000000
Dla człowieka zapis ten staje się zupełnie nieczytelny, lecz komputery radzą sobie z nim znakomicie - bity to ich żywioł. Spróbujmy teraz
dokonać operacji odwrotnej, tzn. odczytać słowo zakodowane w bitach, które np. otrzymaliśmy za pomocą sieci teleinformatycznej z
drugiego końca świata:
1001101110010101100001110
Najpierw rozdzielamy otrzymane bity na grupy po pięć sztuk:
10011 01110 01010 11000 01110
Dla każdej grupy bitów (symbolu binarnego) odszukujemy w tabelce kodu odpowiednią literkę:
10011 - t
01110 - o
01010 - k
11000 - y
01110 - o
11
Architektura Komputera  Kodowanie Liczb
Bajt
Chociaż wolno nam tworzyć kody binarne o dowolnej liczbie bitów na symbol, to jednak z technicznego punktu widzenia wygodnie jest
przyjąć pewne ustalone jednostki. Standardowe grupy bitów można w prosty sposób przechowywać w pamięciach komputerów, na
nośnikach danych oraz przesyłać za pomocą sieci teleinformatycznych.
Bajt jest taką właśnie standaryzacją. Najczęściej przyjmuje się, iż jest to grupa 8 bitów. Komórki pamięci komputera przechowują
informację w postaci bajtów. Również wiele urządzeń przystosowane zostało do danych przekazywanych w takiej formie (porcjami po 8
bitów) - np. drukarki, terminale, modemy, dyski elastyczne i twarde, itp. Dlatego bajt stał się kolejną po bicie jednostką informacji. Bajt
utożsamiany jest ze znakiem, literą, ponieważ używa się często 8 bitowego kodu do przekazywania znaków (ASCII - American Standard
Code for Information Interchange).
ZAPAMI
TAJ
Bajt jest grupą 8 bitów.
Oznaczamy go dużą literką B w odróżnieniu od bitu - b.
1 B pozwala przekazywać informację o 256 zdarzeniach.
Mnożniki binarne
W fizyce i technice stosowane są wielokrotności jednostek podstawowych. Oznaczamy je odpowiednimi przyrostkami kilo, mega, giga i
tera. Podstawą tych wielokrotności jest liczba 10:
kilo = 1000 = 103
mega = 1000000 = 106 = kilo x 1000
giga = 1000000000 = 109 = mega x 1000
tera = 1000000000000 = 1012 = giga x 1000
12
Architektura Komputera  Kodowanie Liczb
W systemie binarnym, ze względu na podobieństwo, zastosowano również podobne mnożniki, jednakże podstawą ich jest liczba 2, nie 10,
gdyż tak jest dużo wygodniej (pod koniec tego opracowania zrozumiesz dlaczego). Starano się przy tym, aby mnożnik binarny był jak
najbliższy odpowiednikowi dziesiętnemu. I tak otrzymano:
Kilo = 1024 = 210
Mega = 1048576 = 220 = Kilo x 1024
Giga = 1073741824 = 230 = Mega x 1024
Tera = 1099511627776 = 240 = Giga x 1024
Dla odróżnienia mnożników binarnych od dziesiętnych zapisujemy je dużą literką. Jednostki binarne dzielimy na bitowe (podstawą jest
bit) oraz bajtowe (podstawą jest bajt).
Jednostki binarne
bitowe bajtowe
1b bit 1B bajt
1Kb kilobit 1KB kilobajt
1Mb megabit 1MB megabajt
1Gb gigabit 1GB gigabajt
1Tb terabit 1TB terabajt
ZAPAMI
TAJ
Podstawą mnożników binarnych jest liczba 2, a nie 10. Więc zamiast 1000 = 103 mamy 1024 = 210.
13
Architektura Komputera  Kodowanie Liczb
Zadania
1. Skoro informacja jest tworem niematerialnym, to w jaki sposób może być przetwarzana za pomocą maszyn liczących?
2. Ile bitów potrzebne jest do zakodowania każdej cyfry dziesiętnej? Podaj odpowiedni przykład.
3. Jak wzrośnie liczba słówek kodowych, jeśli zwiększymy dwukrotnie liczbę tworzących je bitów?
4. Ile bitów zawiera 1MB?
5. Ile bajtów zawiera 1,5GB?
14
Architektura Komputera  Kodowanie Liczb
NATURALNY KOD BINARNY
W poprzednim rozdziale pokazaliśmy sposoby tworzenia złożonych symboli binarnych z grup bitów. Liczby moglibyśmy w zasadzie
zakodować binarnie podobnie jak znaki - każdej z nich przypisując określoną kombinację stanów bitów. Jednakże w przeciwieństwie do
znaków na liczbach chcemy przeprowadzać różne operacje arytmetyczne i otrzymywać wyniki zgodne z zasadami arytmetyki. Dlatego
sposób przypisania bitów liczbom nie może być dowolny, lecz musi tworzyć system ułatwiający wykonywanie obliczeń - w przeciwnym
razie elektroniczne układy arytmetyczne ogromnie by się skomplikowały, a tego nie chcemy.
Rozwiązanie tego problemu istnieje już od dawna, a nawet posługujemy się nim na co dzień - jest to pozycyjny system liczenia.
Systemy pozycyjne
Abakus.
Prosty przyrząd wykorzystujący
własności systemu pozycyjnego
15
Architektura Komputera  Kodowanie Liczb
Ponad tysiąc lat temu pewien hinduski geniusz wymyślił system zapisu liczb, w którym stosuje się jedynie dziesięć różnych znaków,
zwanych cyframi. Za sprawą kupców arabskich system ten został rozpowszechniony w ówczesnym świecie i dzisiaj powszechnie jest
znany pod nazwą systemu arabskiego. Cechą charakterystyczną tego systemu jest to, iż wartość cyfr w zapisie liczby zależy od ich
pozycji. Np.
333
w liczbie tej występują trzy jednakowe cyfry - 3. Pierwsza jednak oznacza trzy setki, druga trzy dziesiątki, a ostatnia trzy jednostki.
System ten jest dla nas tak naturalny, iż utożsamiamy wręcz wartość liczby z jej zapisem.
W systemie dziesiętnym podstawą jest liczba dziesięć. Wagi kolejnych pozycji licząc od prawej strony do lewej mają wartość kolejnych
potęg podstawy. Wartość liczby jest sumą iloczynów wartości cyfr przez wagi swoich pozycji. Powyższy zapis możemy więc zapisać
następująco:
333 = 3 x 102 + 3 x 101 + 3 x 100
Jeśli przez p oznaczymy podstawę systemu (czyli 10), a przez c cyfrę ze zbioru {0,1,...,9}, to wartość dowolnej, n-cyfrowej liczby
dziesiętnej wyrazi się wzorem:
cn-1cn-2...c2c1c0 = cn-1 x pn-1 + cn-2 x pn-2 + ... + c2 x p2 + c1 x p1 + c0 x p0
Powyższy wzór jest również prawdziwy, jeśli dokonamy zmiany wartości podstawy p. Na przykład dla p = 5 otrzymujemy system
piątkowy. W systemie piątkowym mamy cyfry {0,1,2,3,4} - cyfry 5 nie ma z tych samych powodów, dla których w naszym systemie nie
występuje cyfra 10. Obliczmy dla przykładu wartość liczby piątkowej 3214(5).
3214(5) = 3 x 53 + 2 x 52 + 1 x 51 + 4 x 50
3214(5) = 3 x 125 + 2 x 25 + 1 x 5 + 4 x 1
3214(5) = 375 + 50 + 5 + 4
3214(5) = 434
16
Architektura Komputera  Kodowanie Liczb
A teraz liczba trójkowa (p = 3, c - {0,1,2} ) 2012(3) :
2012(3) = 2 x 33 + 0 x 32 + 1 x 31 + 2 x 30
2012(3) = 2 x 27 + 0 x 9 + 1 x 3 + 2 x 1
2012(3) = 54 + 0 + 3 + 2
2012(3) = 59
Z przedstawionych przykładów można wysnuć wniosek, iż każdy system pozycyjny jest równie dobry do zapisu liczb.
System dziesiętny jest tutaj o tyle wyjątkowy, iż stosujemy go do zapisu liczb i wydaje się on nam naturalnym
systemem liczbowym. Jeśli jednak będziemy zmniejszać wartość podstawy, to w końcu dojdziemy do liczby 2. System
liczenia oparty na liczbie 2 jest najprostszym systemem pozycyjnym i z tego powodu doskonale nadaje się do
zastosowania w maszynowych rachunkach.
ZAPAMI
TAJ
W dowolnym systemie pozycyjnym o podstawie p mamy p cyfr c - {0,1,...,p-1}. Wagi kolejnych
pozycji od strony prawej do lewej są kolejnymi od zera potęgami podstawy. Wartość liczby
obliczamy jako sumę iloczynów cyfr przez wagi swoich pozycji.
cn-1cn-2...c1c0 = cn-1pn-1 + cn-2pn-2 + ... + c1p1 + c0p0
17
Architektura Komputera  Kodowanie Liczb
Dwójkowy system pozycyjny
W systemie dwójkowym podstawa wynosi 2. Cyfr jest tylko dwie: 0 i 1. Dzięki temu cyfry dwójkowe mogą być
bezpośrednio przedstawiane przy pomocy bitów, które również przyjmują dwa stany. Wartość liczby oblicza się
szczególnie prosto - w sumie bierzemy tylko te wagi pozycji, na których występują cyfry 1. Oto przykład:
110111(2) = 1 x 25 + 1 x 24 + 0 x 23 + 1 x 22 + 1 x 21 + 1 x 20
110111(2) = 1 x 32 + 1 x 16 + 0 x 8 + 1 x 4 + 1 x 2 + 1 x 1
110111(2) = 32 + 16 + 4 + 2 + 1
110111(2) = 55
Liczby binarne zapisujemy najczęściej z określoną liczbą bitów (np. 4, 8, 16, 32...). Podyktowane to jest względami
technicznymi. Na przykład pamięć komputera zapamiętuje w jednej komórce 8 bitów, więc rozsądnie jest przyjąć
format zapisu liczby, który jest wielokrotnością 8 bitów. Bardzo pomocna jest znajomość pierwszych 16 liczb
zapisanych w systemie binarnym. Proponujemy wyuczenie się na pamięć poniższej tabelki, co bardzo przyda się przy
konwersjach pomiędzy systemami ósemkowym i szesnastkowym. Zwróćcie uwagę, iż dla początkowych liczb starsze
wagi pozycji zawierają cyfry 0.
18
Architektura Komputera  Kodowanie Liczb
Pierwsze 16 liczb binarnych
0 0000 = 0 x 23 + 0 x 22 + 0 x 21 + 0 x 20
1 0001 = 0 x 23 + 0 x 22 + 0 x 21 + 1 x 20
2 0010 = 0 x 23 + 0 x 22 + 1 x 21 + 0 x 20
3 0011 = 0 x 23 + 0 x 22 + 1 x 21 + 1 x 20
4 0100 = 0 x 23 + 1 x 22 + 0 x 21 + 0 x 20
5 0101 = 0 x 23 + 1 x 22 + 0 x 21 + 1 x 20
6 0110 = 0 x 23 + 1 x 22 + 1 x 21 + 0 x 20
7 0111 = 0 x 23 + 1 x 22 + 1 x 21 + 1 x 20
8 1000 = 1 x 23 + 0 x 22 + 0 x 21 + 0 x 20
9 1001 = 1 x 23 + 0 x 22 + 0 x 21 + 1 x 20
10 1010 = 1 x 23 + 0 x 22 + 1 x 21 + 0 x 20
11 1011 = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20
12 1100 = 1 x 23 + 1 x 22 + 0 x 21 + 0 x 20
13 1101 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20
14 1110 = 1 x 23 + 1 x 22 + 1 x 21 + 0 x 20
19
Architektura Komputera  Kodowanie Liczb
ZAPAMI
TAJ
W systemie dwójkowym waga pozycji ma wartość 2. Występują tylko dwie cyfry 0 i 1.
Wartość liczby obliczamy zgodnie ze wzorem:
cn-1cn-2...c1c0 = cn-12n-1 + cn-22n-2 + ... + c121 + c020
Zakres naturalnych liczb dwójkowych
Oparliśmy system zapisu liczb binarnych na pozycyjnym systemie dwójkowym, ponieważ pozwalał on bezpośrednio
kodować cyfry przy pomocy bitów. W następnym kroku określimy zakres liczb, które można przedstawić przy
pomocy n bitów. Na początek dolna granica. Najmniejszą liczbę otrzymamy, gdy wszystkie cyfry przyjmą wartość 0.
Wartość takiej liczby jest równa zero. Dolną granicą jest zatem liczba zero.
Górną granicę dla n bitów otrzymamy ustawiając wszystkie cyfry na 1. Będzie to największa liczba możliwa do
zapisania przy pomocy n bitów. Jaką wartość ma taka liczba. Szybko przekonamy się wypisując kilka początkowych
wartości:
dla n = 1 mamy 1(2) = 1 = 21 - 1
dla n = 2 mamy 11(2) = 3 = 22 - 1
dla n = 3 mamy 111(2) = 7 = 23 - 1
dla n = 4 mamy 1111(2) = 15 = 24 - 1
20
Architektura Komputera  Kodowanie Liczb
W każdym przypadku otrzymujemy za górną granicę liczbę równą 2n - 1. Podsumujmy:
ZAPAMI
TAJ
Dla n bitów możemy utworzyć w naturalnym kodzie binarnym liczby z zakresu:
<0, 2n - 1>
Sytuację odwrotną mamy, gdy dana jest określona liczba naturalna W, a chcemy poznać ilość bitów potrzebnych do
jej zapisu w naturalnym systemie binarnym. W tym celu wystarczy, aby była spełniona prosta nierówność:
W d" 2n - 1,
gdzie n jest poszukiwaną liczbą bitów
Liczbę n obliczamy następująco:
n = [log2W + 1]
ZAPAMI
TAJ
Do zapisu liczby naturalnej n potrzebne jest co najmniej [log2n + 1] bitów.
21
Architektura Komputera  Kodowanie Liczb
Ósemkowy system pozycyjny
Liczby binarne są niewygodne dla ludzi. Cyfry 0 i 1 dają zbyt małą różnorodność i nasze mózgi szybko się nużą przy analizowaniu
długich ciągów bitów. Dlatego programiści często zastępują zapis binarny zapisem ósemkowym. Chociaż na początku może się to
wydawać dziwne, to jednak ma sens. Otóż system ósemkowy i dwójkowy posiadają wspólną cechę - podstawą ich jest potęga liczby 2.
Dzięki temu szczególnie prosto można przeliczać liczby pomiędzy tymi systemami.Do zamiany liczb binarnych i ósemkowych potrzebna
nam będzie prosta tabelka, w której każdą cyfrę ósemkową przedstawiamy w postaci trzech bitów.
cyfra wartość
ósemkowa dwójkowa
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
ZAPAMI
TAJ W systemie ósemkowym waga pozycji ma wartość 8. Występuje osiem cyfr {0,1,2,3,4,5,6,7}.
Wartość liczby obliczamy zgodnie ze wzorem:
cn-1cn-2...c1c0 = cn-18n-1 + cn-28n-2 + ... + c181 + c080
22
Architektura Komputera  Kodowanie Liczb
Zamiana liczby dwójkowej na ósemkową
Mamy liczbę dwójkową 10111011010101(2). Zamienimy ją na liczbę w systemie ósemkowym o tej samej wartości. W
tym celu bity dzielimy na grupy trzybitowe poczynając od końca. Jeśli w ostatniej grupie nie będzie trzech bitów, to
dopisujemy na początku odpowiednią liczbę zer:
10111011010101
010 111 011 010 101
Każdą z grup trzybitowych zastępujemy cyfrą ósemkową z tabelki:
010 111 011 010 101
2 7 3 2 5
W wyniku otrzymujemy liczbę ósemkową o tej samej wartości:
10111011010101(2). = 27325(8)
23
Architektura Komputera  Kodowanie Liczb
Sprawdz
my to:
10111011010101(2). = 8192 + 2048 + 1024 + 512 + 128 + 64 + 16 + 4 + 1 = 11989
27325(8) = 2 x 4096 + 7 x 512 + 3 x 64 + 2 x 8 + 5 x 1 = 8192 + 3584 + 192 + 16 + 5 = 11989
Otrzymaliśmy w obu wypadkach ten sam wynik, wobec tego zapis 10111011010101(2) oraz 27325(8) odnosi się do tej
samej liczby o wartości dziesiętnej 11989.
ZAPAMI
TAJ
Przeliczeń pomiędzy systemem ósemkowym a binarnym dokonujemy zastępując cyfry ósemkowe ich trzybitową
wartością w systemie dwójkowym. W odwrotną stronę zastępujemy grupy trzybitowe cyfrą ósemkową, która
odpowiada im wartością.
Zamiana liczby ósemkowej na dwójkową
Operacja odwrotna jest równie prosta. W tym przypadku każdą cyfrę ósemkową zastępujemy trzybitową wartością z tabelki. W
Wyniku otrzymamy liczbę dwójkową o tej samej wartości. Zamieńmy liczbę ósemkową 336724076102(8) na odpowiadającą jej liczbę
binarną:
3 3 6 7 2 4 0 7 6 1 0 2
011 011 110 111 010 100 000 111 110 001 000 010
Zatem 336724076102(8) = 011011110111010100000111110001000010(2)
Zwróćcie uwagę, iż zapis ósemkowy jest krótszy i bardziej czytelny dla ludzi od zapisu dwójkowego. Z tego właśnie powodu programiści
wolą stosować liczby ósemkowe zamiast binarnych - zawsze przecież można je szybko przeliczyć w jedną i drugą stronę.
24
Architektura Komputera  Kodowanie Liczb
Szesnastkowy system pozycyjny
Drugim popularnym systemem służącym do zastępowania liczb binarnych jest system szesnastkowy. Podstawa w tym
systemie ma wartość 16. Potrzebujemy zatem 16 cyfr, jednakże dorobiliśmy się ich tylko 10 - {0,1,2,3,4,5,6,7,8,9}.
Brakujące 6 cyfr zastępujemy kolejnymi literkami alfabetu A,B,C,D,E i F. Cyfry te mają kolejne wartości: A = 10, B
= 11, C = 12, D = 13, E = 14 i F = 15. Po tych ustaleniach możemy już zapisywać liczby w systemie szesnastkowym
oraz obliczać ich wartość. Np. obliczmy wartość liczby 25FE(16). Korzystamy ze znanego wzoru:
25FE(16) = 2 x 4096 + 5 x 256 + 15 x 16 + 14 x 1 = 9726
ZAPAMI
TAJ
W systemie szesnastkowym, zwanym również heksadecymalnym, podstawa p = 16. Zbiór cyfr tworzą znaki:
{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. Dodatkowe cyfry A,...,F mają wartości dziesiętne równe kolejno od 10 do 15.
Wartość liczby szesnastkowej obliczamy według wzoru:
cn-1cn-2...c1c0 = cn-116n-1 + cn-216n-2 + ... + c1161 + c0160
25
Architektura Komputera  Kodowanie Liczb
Konwersję pomiędzy systemem szesnastkowym a dwójkowym wykonujemy podobnie jak dla systemu ósemkowego - 16 jest również
potęgą liczby 2. Potrzebna nam będzie tabelka wartości cyfr szesnastkowych w systemie dwójkowym. Każdej cyfrze szesnastkowej
odpowiada grupa czterech bitów:
cyfra wartość
szesnastkowa dwójkowa
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
A 1010
B 1011
C 1100
D 1101
E 1110
F 1111
26
Architektura Komputera  Kodowanie Liczb
Zamiana liczby dwójkowej na szesnastkową
Liczbę dwójkową dzielimy na grupy czterobitowe poczynając od prawej strony. Jeśli w ostatniej grupie wypadnie
mniej bitów, to dopełniamy je zerami. Następnie każdą grupę zastępujemy odpowiednią cyfrą szesnastkową. Dla
przykładu zamieńmy liczbę binarną 111010100011101010101101101001110(2) na odpowiadającą jej wartość w
systemie szesnastkowym:
111010100011101010101101101001110
0001 1101 0100 0111 0101 0101 1011 0100 1110
1 D 4 7 5 5 B 4 E
111010100011101010101101101001110(2) = 1D4755B4E(16)
Czytelnikom pozostawiamy sprawdzenie, iż są to te same liczby.
Zamiana liczby szesnastkowej na dwójkową
Zamiana polega na zastąpieniu każdej cyfry szesnastkowej odpowiadającą jej grupą czterech bitów z tabelki. W
wyniku otrzymamy liczbę dwójkową o tej samej wartości. Dla przykładu zamieńmy liczbę FDA73201(16) na postać
binarną:
F D A 7 3 2 0 1
1111 1101 1010 0111 0011 0010 0000 0001
Zatem FDA73201(16) = 11111101101001110011001000000001(2).
27
Architektura Komputera  Kodowanie Liczb
Dwójkowe liczby stałoprzecinkowe
System stałopozycyjny zapisu liczb jest rozszerzeniem zapisu liczb naturalnych w stronę wartości ułamkowych. W
systemie dziesiętnym za cyfrą jednostek umieszcza się przecinek, a kolejne wagi pozycji są teraz ujemnymi potęgami
podstawy:
253,763 = 2 x 102 + 5 x 101 + 3 x 100 + 7 x 10-1 + 6 x 10-2 + 3 x 10-3
Zasada ta obowiązuje również w innych systemach pozycyjnych. Dla przykładu obliczmy wartość stałopozycyjnej
liczby piątkowej: 432,321(5):
432,321(5) = 4 x 52 + 3 x 51 + 2 x 50 + 3 x 5-1 + 2 x 5-2 + 1 x 5-3
432,331(5) = 4 x 25 + 3 x 5 + 2 x 1 + 3 x 1/5 + 2 x 1/25 + 1 x 1/125
432,331(5) = 100 + 15 + 2 + 3/5 + 2/25 + 1/125
432,331(5) = 117 86/125
432,331(5) = 117,688
ZAPAMI
TAJ
W dowolnym systemie pozycyjnym o podstawie p wartość liczby stałoprzecinkowej obliczamy wg wzoru:
cn-1...c0,c-1c-2...c-m = cn-1pn-1 + ... + c0p0 + c-1p-1 + c-2p-2 + ... +c-mp-m
gdzie n - liczba cyfr przed przecinkiem, m - liczba cyfr po przecinku
28
Architektura Komputera  Kodowanie Liczb
Znając tą zasadę nie napotkamy żadnych trudności w systemie dwójkowym. Obliczymy wartość dwójkowej liczby
stałoprzecinkowej 1101,1011(2):
1101,1011(2) = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 + 1 x 2-1 + 0 x 2-2 + 1 x 2-3 + 1 x 2-4
1101,1011(2) = 1 x 8 + 1 x 4 + 0 x 1 + 1 x 1 + 1 x 1/2 + 0 x 1/4 + 1 x 1/8 + 1 x 1/16
1101,1011(2) = 8 + 4 + 1 + 1/2 + 1/8 + 1/16
1101,1011(2) = 13 + 10/16
1101,1011(2) = 13,625
Zakres dwójkowych liczb stałoprzecinkowych
Określimy zakres liczb stałoprzecinkowych, w których n bitów przechowuje część całkowitą, a m bitów część
ułamkową. Wartość takiej liczby można zapisać jako sumę części całkowitej oraz części ułamkowej:
Jeśli liczbę zapiszemy za pomocą cyfr binarnych c, należących do zbioru {0,1}, to
W - wartość liczby = cn-1cn-2...c2c1c0,c-1c-2...c-m+1c-m
Wc - wartość części całkowitej = cn-1cn-2...c2c1c0
Wu - wartość części ułamkowej = c-1c-2...c-m+1c-m
W = Wc + Wu
Wc = cn-12n-1 + cn-22n-2 + ... + c222 + c121 + c020
Wu = c-12-1 + c-22-2 + ... + c-m+12-m+1 + c-m2-m
29
Architektura Komputera  Kodowanie Liczb
Zakres części całkowitej policzyliśmy już wcześniej i wynosi on <0,2n - 1>. Policzymy zatem zakres części ułamkowej. Najmniejszą liczbę
otrzymamy, gdy wszystkie cyfry będą zerami. Wartość ta wynosi oczywiście zero. Największą liczbę otrzymamy przy wszystkich cyfrach
równych 1.
Sprawdz
my ile to będzie dla kolejnych wartości m:
m = 1, 0,1 = 1 x 2-1 = 1 x 1/2 = 1/2
m = 2, 0,11 = 1 x 2-1 + 1 x 2-2 = 1 x 1/2 + 1 x 1/4 = 3/4
m = 3 0,111 = 1 x 2-1 + 1 x 2-2 + 1 x 2-3 = 1 x 1/2 + 1 x 1/4 + 1 x 1/8 = 7/8
Jeśli przyjrzycie się otrzymanym wynikom, to na pewno zauważycie, iż mianownik otrzymanego ułamka ma wartość 2m, natomiast
licznik jest o 1 mniejszy, czyli 2m - 1. Stąd zakres części ułamkowej wynosi:
2m -
<0,
>
1
2m
Jeśli teraz połączymy zakresy części całkowitej i ułamkowej, to otrzymamy zakres liczby stałoprzecinkowej o n cyfrach całkowitych i m
cyfrach ułamkowych, który wynosi:
2m -
<0, 2n - 1 +
1
>
2m
30
Architektura Komputera  Kodowanie Liczb
Zadania
1. Oblicz wartość następujących liczb:
1234(5), 3456(7), 5678(9)
2. Oblicz wartość następujących liczb binarnych:
110011(2), 1110111(2), 11001110011(2)
3. Jak wzrośnie zakres n bitowej liczby binarnej, jeśli zwiększymy jej długość o 3 bity?
4. Załóżmy, iż pewna liczba binarna posiada 3n bitów. Taką liczbę da się przedstawić w systemie ósemkowym za pomocą n cyfr. Jak
rozpoznać w zapisie ósemkowym, iż najstarszy bit liczby binarnej ma wartość 1?
5. Jak określić liczbę cyfr ósemkowych liczby binarnej zapisanej w systemie szesnastkowym za pomocą n cyfr?
6. Oblicz wartość następującej liczby binarnej:
1100111,011101(2)
31
Architektura Komputera  Kodowanie Liczb
ALGORYTM HORNERA
Algorytm Hornera dla dowolnego systemu pozycyjnego
We wzorze obliczania wartości liczby zapisanej w dowolnym systemie pozycyjnym występują kolejne potęgi podstawy. Konieczność
wykonywania operacji potęgowania może być kłopotliwa, szczególnie, gdy obliczamy wartość liczby ze strumienia danych wejściowych.
W strumieniu takim otrzymujemy kolejne cyfry liczby oraz informację o ich końcu. Rozwiązaniem problemu jest algorytm Hornera,
który w pierwotnej postaci służy do obliczania wartości wielomianów potęgowych.
Załóżmy, że mamy daną pięciocyfrową liczbę c4c3c2c1c0 zapisaną w dowolnym systemie pozycyjnym o podstawie p (dla większej ilości
cyfr postępujemy identycznie). Obliczmy wartość liczby wg znanego nam wzoru potęgowego:
c4c3c2c1c0 = c4p4 + c3p3 + c2p2 + c1p1 + c0p0
Potęgę p1 zapiszmy jako p, a p0 jest równe 1, wobec czego wzór ten przyjmie postać:
c4c3c2c1c0 = c4p4 + c3p3 + c2p2 + c1p + c0
Wyprowadzamy czynnik p kolejno przed nawiasy:
c4c3c2c1c0 = (c4p3 + c3p2 + c2p + c1)p + c0
c4c3c2c1c0 = ((c4p2 + c3p + c2)p + c1)p + c0
c4c3c2c1c0 = (((c4p + c3)p + c2)p + c1)p + c0
Zwróćcie uwagę, iż w otrzymanym na końcu wzorze nie występuje już potęgowanie, lecz same mnożenia i dodawania. W jaki sposób
obliczamy wartość liczby?
32
Architektura Komputera  Kodowanie Liczb
Wykonując obliczenia w nawiasach:
w0 = c4
w1 = w0p + c3
w2 = w1p + c2
w3 = w2p + c1
w4 = w3p + c0 - koniec, w4 jest wartością liczby
Przy wykorzystaniu algorytmu Hornera w programach komputerowych podany schemat obliczeń jest nieco zmodyfikowany.
Mianowicie za wartość początkową liczby przyjmujemy zero, a następnie wykonujemy mnożenia przez podstawę i dodajemy kolejne
cyfry. Przy tej modyfikacji otrzymamy:
w0 = 0
w1 = w0p + c4
w2 = w1p + c3
w3 = w2p + c2
w4 = w3p + c1
w5 = w4p + c0 - koniec, w5 jest wartością liczby.
W tej wersji algorytm jest bardziej spójny z danymi - dla każdej kolejnej cyfry wykonywana jest ta sama operacja - przemnożenie
poprzedniej wartości liczby przez podstawę systemu i dodanie wartości cyfry.
33
Architektura Komputera  Kodowanie Liczb
ZAPAMI
TAJ
Algorytm Hornera obliczania wartości liczby zapisanej jako ciąg cyfr w dowolnym systemie pozycyjnym jest
następujący:
1. Za początkową wartość liczby przyjmij zero
2. Pobierz kolejną cyfrę liczby
3. Jeśli cyfra istnieje, to pomnóż wartość liczby przez podstawę systemu, dodaj do niej wartość cyfry i przejdz

do punktu 2
4. Jeśli cyfry skończyły się, to zakończ algorytm. Wartość liczby została obliczona.
Przykład
Obliczmy tą metodą wartość liczby szóstkowej 25314(6). Podstawa systemu szóstkowego wynosi 6.
w0 = 0
w1 = 0 x 6 + 2 = 2
w2 = 2 x 6 + 5 = 17
w3 = 17 x 6 + 3 = 105
w4 = 105 x 6 + 1 = 631
w5 = 631 x 6 + 4 = 3790
A teraz sprawdz
my ten wynik normalną metodą przy zastosowaniu wzoru potęgowego:
25314(6) = 2 x 64 + 5 x 63 + 3 x 62 + 1 x 61 + 4 x 60
25314(6) = 2 x 1296 + 5 x 216 + 3 x 36 + 1 x 6 + 4 x 1
25314(6) = 2592 + 1080 + 108 + 6 + 4
25314(6) = 3790
34
Architektura Komputera  Kodowanie Liczb
Algorytm Hornera dla naturalnych liczb dwójkowych
Ponieważ system dwójkowy jest systemem pozycyjnym, to obowiązują w nim te same zasady, co w innych systemach pozycyjnych.
Dzięki temu algorytm Hornera będzie identyczny z opisanym wcześniej, a nawet prostszy, ponieważ mnożenie przez dwa możemy
zastąpić dodawaniem, co znacznie przyspiesza obliczenia.
ZAPAMI
TAJ
Algorytm Hornera obliczania wartości liczby dwójkowej jest następujący:
1. Za początkową wartość liczby przyjmij zero
2. Pobierz kolejną cyfrę liczby
3. Jeśli cyfra istnieje, to dodaj do siebie poprzednią wartość liczby a do wyniku dodaj wartość pobranej cyfry i przejdz
do punktu 2
4. Jeśli cyfry skończyły się, to zakończ algorytm. Wartość liczby została obliczona.
35
Architektura Komputera  Kodowanie Liczb
Przykład
Obliczmy opisanym sposobem wartość liczby 11001011011(2):
w0 = 0
w1 = 0 + 0 + 1 = 1
w2 = 1 + 1 + 1 = 3
w3 = 3 + 3 + 0 = 6
w4 = 6 + 6 + 0 = 12
w5 = 12 + 12 + 1 = 25
w6 = 25 + 25 + 0 = 50
w7 = 50 + 50 + 1 = 101
w8 = 101 + 101 + 1 = 203
w9 = 203 + 203 + 0 = 406
w10= 406 + 406 + 1 = 813
w11= 813 + 813 + 1 = 1627
36
Architektura Komputera  Kodowanie Liczb
Algorytm Hornera dla liczb stałoprzecinkowych
Jeśli mamy daną liczbę stałoprzecinkową zapisaną w postaci n cyfr części całkowitej i m cyfr części ułamkowej, to do obliczenia jej
wartości możemy również zastosować algorytm Hornera po drobnej modyfikacji. Otóż obliczamy wartość liczby tak, jakby nie było
przecinka, a następnie wynik dzielimy przez wartość podstawy podniesionej do potęgi m.
Przykład
Obliczmy tą metodą wartość liczby siódemkowej 52,354(7):
n = 2, m = 3
w0 = 0
w1 = 0 x 7 + 5 = 5
w2 = 5 x 7 + 2 = 37
w3 = 37 x 7 + 3 = 262
w4 = 262 x 7 + 5 = 1839
w5 = 1839 x 7 + 4 = 12877 - ostatnia cyfra, kończymy
Wynik dzielimy przez 7m = 73 = 343
w5 1287
w6 = = 3 186
7
= 7
7m 343 343
37
Architektura Komputera  Kodowanie Liczb
Sprawdz
my otrzymany wynik za pomocą tradycyjnej metody obliczania wartości liczby stałoprzecinkowej:
52,354(7) = 5 x 71 + 2 x 70 + 3 x 7-1 + 5 x 7-2 + 4 x 7-3
52,354(7) = 5 x 7 + 2 x 1 + 3 x 1/7 + 5 x 1/49 + 4 x 1/343
52,354(7) = 35 + 2 + 3/7 + 5/49 + 4/343
52,354(7) = 37 + 147/343 + 35/343 + 4/343
52,354(7) = 37 186/343
ZAPAMI
TAJ
Algorytm Hornera obliczania wartości liczby stałoprzecinkowej zapisanej jako ciąg cyfr w dowolnym systemie
pozycyjnym jest następujący:
1. Oblicz wartość liczby tak, jakby nie było przecinka
2. Wynik podziel przez podstawę systemu pozycyjnego podniesioną do potęgi równej liczbie cyfr po przecinku
38
Architektura Komputera  Kodowanie Liczb
Przeliczanie liczb na dowolny system pozycyjny
Rozważmy następujący problem: mamy liczbę dziesiętną o wartości W. Chcemy znalez
ć kolejne cyfry
cn-1cn-2...c2c1c0
zapisu tej liczby w systemie pozycyjnym o podstawie p. Zapiszmy:
W = cn-1pn-1 + cn-2pn-2 + ... + c2p2 + c1p + c0
Podzielmy wartość W przez p. Otrzymamy wtedy:
Wc0
= cn-1pn-2 + cn-2pn-3 + ... + c2p + c1
+
p p
Ponieważ wartość każdej cyfry jest zawsze mniejsza od podstawy systemu liczbowego, ułamek c0 / p jest ułamkiem
właściwym. Wobec tego wartość cyfry c0 otrzymamy jako resztę z dzielenia W przez p. Za nową wartość W
przyjmijmy część całkowitą z dzielenia, czyli
W ] = cn-1pn-2 + cn-2pn-3 + ... + c2p +
W1 = [
c1
p
Zwróćcie uwagę, iż otrzymaliśmy nową wartość, której zapis w systemie o podstawie p składa się z tych samych cyfr
co W z pominięciem ostatniej c0. Możemy teraz znów przeprowadzić identyczną operację i otrzymać kolejną cyfrę c1
jako resztę z dzielenia W1 przez p. Za nowe W przyjmujemy część całkowitą z dzielenia W1 przez p, czyli:
W1 ] = cn-1pn-3 + cn-2pn-2 + ... +
W2 = [
c2
p
39
Architektura Komputera  Kodowanie Liczb
I znów mamy sytuację identyczną jak poprzednio. Możemy więc opisane działania kontynuować, aż do uzyskania
wszystkich cyfr. Wyliczanie cyfr przerywamy w chwili otrzymania wartości zero w wyniku dzielenia Wi przez
podstawę p.
Przykład
Dla przykładu znajdz
my wg opisanej metody cyfry w systemie czwórkowym liczby dziesiętnej 1000.
W = 1000
c0 = reszta z dzielenia 1000 przez 4 = 0,
W1 = [1000 : 4) = [250] = 250
c1 = reszta z dzielenia 250 przez 4 = 2
W2 = [250 : 4] = [62,5] = 62
c2 = reszta z dzielenia 62 przez 4 = 2
W3 = [62 : 4] = [15,5] = 15
c3 = reszta z dzielenia 15 przez 4 = 3
W4 = [15 : 4] = [3,75] = 3
c4 = reszta z dzielenia 3 przez 4 = 3
W5 = [3 : 4] = [0,75] = 0 - kończymy, gdyż wynik wynosi zero.
40
Architektura Komputera  Kodowanie Liczb
Otrzymaliśmy cyfry: 33220(4). Zauważcie, iż cyfry otrzymywaliśmy w odwrotnej do zapisu kolejności, tzn. od
najmłodszej do najstarszej. Sprawdz
my rachunkiem, czy otrzymana liczba czwórkowa ma w systemie dziesiętnym
wartość 1000.
33220(4) = 3 x 44 + 3 x 43 + 2 x 42 + 2 x 41 + 0 x 40
33220(4) = 3 x 256 + 3 x 64 + 2 x 16 + 2 x 4 + 0 x 1
33220(4) = 768 + 192 + 32 + 8
33220(4) = 1000
ZAPAMI
TAJ
Zapis liczby dziesiętnej W w dowolnym systemie pozycyjnym o podstawie p znajdujemy następująco:
1. Wartość kolejnej od końca cyfry znajdujemy jako resztę z dzielenia W przez p.
2. Za nowe W przyjmujemy część całkowitą z dzielenia W przez p.
3. Jeśli W jest większe od zera, to przechodzimy do punktu 3. W przeciwnym razie kończymy.
Przeliczanie liczb dwójkowych
Wartości dziesiętne przeliczamy na system dwójkowy w identyczny sposób jak na inne systemy pozycyjne. Jedynym
ułatwieniem może być rozpoznawanie reszt z dzielenia przez 2. Jeśli dzielona liczba jest nieparzysta, to reszta zawsze
wyniesie 1. Dla liczb parzystych reszta z dzielenia przez 2 wynosi 0.
41
Architektura Komputera  Kodowanie Liczb
Przykład
Znajdz
my reprezentację binarną liczby 253651:
253651 : 2 = 126825 i reszta c0 = 1
126825 : 2 = 63412 i reszta c1 = 1
63412 : 2 = 31706 i reszta c2 = 0
31706 : 2 = 15853 i reszta c3 = 0
15853 : 2 = 7926 i reszta c4 = 1
7926 : 2 = 3963 i reszta c5 = 0
3963 : 2 = 1981 i reszta c6 = 1
1981 : 2 = 990 i reszta c7 = 1
990 : 2 = 495 i reszta c8 = 0
495 : 2 = 247 i reszta c9 = 1
247 : 2 = 123 i reszta c10 = 1
123 : 2 = 61 i reszta c11 = 1
61 : 2 = 30 i reszta c12 = 1
30 : 2 = 15 i reszta c13 = 0
15 : 2 = 7 i reszta c14 = 1
7 : 2 = 3 i reszta c15 = 1
3 : 2 = 1 i reszta c16 = 1
1 : 2 = 0 i reszta c17 = 1 - koniec, wynik dzielenia równy zero
253651 = 111101111011010011(2)
42
Architektura Komputera  Kodowanie Liczb
Przeliczanie liczb stałoprzecinkowych
Przy wyznaczaniu rozwinięcia liczb stałoprzecinkowych w dowolnych systemach pozycyjnych musimy dokonać
prostych modyfikacji przedstawionych algorytmów. Załóżmy, iż mamy pewną wartość W, która w docelowym
systemie pozycyjnym p posiada następujące rozwinięcie:
W = cn-1pn-1 + ...c0p0 + c-1p-1 + ... +c-mp-m
gdzie ci, i = -m...n-1 są cyframi rozwinięcia w systemie p, n określa liczbę cyfr części całkowitej, a m określa liczbę
cyfr części ułamkowej. Podane algorytmy pozwalają jedynie wyznaczać rozwinięcie liczb naturalnych. Dlatego przed
ich zastosowaniem musimy wartość liczby pomnożyć przez pm, aby pozbyć się części ułamkowej:
W x pm = (cn-1pn-1 + ...c0p0 + c-1p-1 + ... +c-mp-m)pm
W x pm = cn-1pn-1pm + ...c0p0pm + c-1p-1pm + ... +c-mp-mpm
W x pm = cn-1pn-1+m + ...c0pm + c-1pm-1 + ... +c-mp0
Zwróćcie uwagę, iż takie przemnożenie nie zmienia cyfr rozwinięcia. W wyniku otrzymujemy liczbę całkowitą (jeśli
po przemnożeniu zostanie część ułamkowa, to liczby W nie można przedstawić dokładnie za pomocą m cyfr części
ułamkowej w systemie pozycyjnym p - w takim przypadku zaokrąglamy W do najbliższej liczby całkowitej). Po
wykonaniu mnożenia dokonujemy konwersji na system p. Następnie oddzielamy m ostatnich cyfr. Będzie to część
ułamkowa. Reszta cyfr tworzy część całkowitą.
43
Architektura Komputera  Kodowanie Liczb
Przykład
Przeliczmy wartość dziesiętną 113,688 na system piątkowy z trzema cyframi po przecinku.
m = 3
W = 113,688 x 53 = 113,688 x 125 = 14211
Otrzymaliśmy liczbę całkowitą, więc wartość 113,688 da się przedstawić w systemie piątkowym z trzema cyframi po
przecinku. Obliczamy kolejne cyfry:
14211 : 5 = 2842 i reszta c0 = 1
2842 : 5 = 568 i reszta c1 = 2
568 : 5 = 113 i reszta c2 = 3
113 : 5 = 22 i reszta c3 = 3
22 : 5 = 4 i reszta c4 = 2
4 : 5 = 0 i reszta c5 = 4 - koniec, wynik dzielenia zero
Otrzymaliśmy 423321. Oddzielamy od końca trzy cyfry (m = 3) części ułamkowej i otrzymujemy ostatecznie:
113,688 = 423,321(5)
44
Architektura Komputera  Kodowanie Liczb
ZAPAMI
TAJ
Aby znalez
ć rozwinięcie cyfr w dowolnym systemie pozycyjnym p wartości W z dokładnością do m cyfr po przecinku, należy:
1. Wartość W pomnożyć przez pm. Jeśli otrzymamy liczbę całkowitą, to W można przedstawić dokładnie w systemie pozycyjnym
p. Jeśli otrzymamy liczbę z częścią ułamkową, to wartości W nie da się przedstawić dokładnie na zadanej liczbie cyfr
ułamkowych w systemie pozycyjnym p. W takim przypadku zaokrąglamy iloczyn do najbliższej liczby całkowitej.
2. Obliczamy kolejne cyfry nowej wartości W.
3. Rozdzielamy przecinkiem m ostatnich cyfr od reszty otrzymanych cyfr. Jeśli cyfr tych jest mniej niż m, to dopisujemy przed
nimi odpowiednią liczbę zer.
Przykład
Obliczmy jeszcze rozwinięcie dwójkowe wartości 0,1 (jedna dziesiąta) na 8 cyfrach po przecinku.
m = 8
W = 0,1 x 28 = 0,1 x 256 = 25,6
Otrzymaliśmy liczbę ułamkową.
45
Architektura Komputera  Kodowanie Liczb
Oznacza to, iż wartość dziesiętna 0,1 nie może być przedstawiona dokładnie w systemie binarnym na 8 cyfrach po
przecinku. Co gorsza, nie da się tego zrobić na dowolnej liczbie cyfr po przecinku, ponieważ nie istnieje taka potęga
liczby 2, aby jej iloczyn przez 0,1 dawał wartość całkowitą (wszystkie potęgi liczby 2 kończą się jedną z cyfr 2,4,6 lub
8). Wobec tego w systemie binarnym ułamek 0,1 ma nieskończone rozwinięcie. W naszym przypadku najbliższą
liczbą całkowitą będzie W = 26 i dla niej znajdziemy kolejne cyfry dwójkowe:
26 : 2 = 13 i reszta c0 = 0
13 : 2 = 6 i reszta c1 = 1
6 : 2 = 3 i reszta c2 = 0
3 : 2 = 1 i reszta c3 = 1
1 : 2 = 0 i reszta c4 = 1 - kończymy, wynik dzielenia zero
Otrzymaliśmy 5 cyfr: 11010. Ponieważ po przecinku ma ich być 8, dopisujemy na początku 4 zera (jedno dla części
całkowitej), a następnie oddzielamy przecinkiem 8 końcowych cyfr i ostatecznie:
0,1(10) 0,00011010(2)
ZAPAMI
TAJ
W systemie dwójkowym nie da się dokładnie przedstawić niektórych wartości dziesiętnych. Obliczenia na takich
liczbach prowadzą więc do tzw. błędów zaokrągleń. Podobną cechę mają np. ułamki 1/3, 1/6, 1/7 itp.
46
Architektura Komputera  Kodowanie Liczb
Zadania
1. Oblicz za pomocą algorytmu Hornera wartość następujących liczb pozycyjnych:
6243(8) , 132211(4), 9FF35(16)
2. Oblicz algorytmem Hornera wartość liczby dwójkowej:
11001110001111000011111(2)
3. Oblicz algorytmem Hornera wartość następujących, pozycyjnych liczb stałoprzecinkowych:
221,1022(3), 412,301(5), 634,1252(7)
4. Przelicz na system szóstkowy następujące liczby dziesiętne:
100, 500, 1000, 10000
5. Przelicz na system dwójkowy następujące liczby dziesiętne:
100, 1000, 10000
6. Przelicz na system trójkowy z dokładnością do 4 cyfr po przecinku następujące dwie liczby dziesiętne:
10,5 15,86
47