Microsoft Word - KODOWANIE LICZB.doc

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ń

nary (dwójkowy) oraz digi

(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,

, 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

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

jest symbolem, który może przyjmować dwie różne postacie. Jeśli chcemy zapisać go na papierze, to

stosujemy symbole pomocnicze

. 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

(oznaczany również

L - Low

- Niski)

2,0 ... 2,4 V - stan

(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.

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.

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ą

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:

- symbol pierwszy

- symbol drugi

- symbol trzeci

- 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.

Architektura Komputera – Kodowanie Liczb

Przykład

Załóż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

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:

- symbol pierwszy

- symbol drugi

- symbol trzeci

- symbol czwarty

- symbol piąty

- symbol szósty

- symbol siódmy

- 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.

Architektura Komputera – Kodowanie Liczb

liczba bitów liczba symboli liczba bitów liczba symboli

131072

262144

524288

1048576

2097152

128

8388608

256

16777216

512

33554432

1024

67108864

2048

134217728

4096

268435456

8192

536870912

16384

1073741824

32768

2147483648

65536

4294967296

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ą 2

. 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

(log

(n - 1) + 1).

ZAPAMIĘTAJ

bitów daje

symboli

symboli wymaga

[log

(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.

Architektura Komputera – Kodowanie Liczb

W tym przypadku wiadomościami będą literki. W alfabecie łacińskim jest ich 26:

bcdefghijklmnopqrstuvwxyz

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

[log

(26 - 1) + 1] = [log

25 + 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

00000

00111

01110

10101

00001

01000

01111

10110

00010

01001

10000

10111

00011

01010

10001

11000

00100

01011

10010

11001

00101

01100

10011

00110

01101

10100

Architektura Komputera – Kodowanie Liczb

Zamieńmy na bity wg opracowanego schematu słowo "sowa":

- 10010

- 01110

- 10110

- 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

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

merican

tandard

ode for

nformation

nterchange).

ZAPAMIĘTAJ

Bajt

jest grupą 8 bitów.

Oznaczamy go dużą literką

w odróżnieniu od bitu -

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

= 10

mega

= 1000000

= 10

= kilo x 1000

giga

= 1000000000

= 10

= mega x 1000

tera

= 1000000000000 = 10

= giga x 1000

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

= 2

Mega

= 1048576

= 2

= Kilo x 1024

Giga

= 1073741824

= 2

= Mega x 1024

Tera

= 1099511627776 = 2

= 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

bit

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

, a nie

. Więc zamiast

1000 = 10

mamy

1024 = 2

Architektura Komputera – Kodowanie Liczb

Zadania

. Skoro informacja jest tworem niematerialnym, to w jaki sposób może być przetwarzana za pomocą maszyn liczących?

. Ile bitów potrzebne jest do zakodowania każdej cyfry dziesiętnej? Podaj odpowiedni przykład.

. Jak wzrośnie liczba słówek kodowych, jeśli zwiększymy dwukrotnie liczbę tworzących je bitów?

. Ile bitów zawiera 1MB?

. Ile bajtów zawiera 1,5GB?

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

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 10

+ 3 x 10

Jeśli przez

oznaczymy podstawę systemu (czyli 10), a przez

cyfrę ze zbioru

{0,1,...,9}

, to wartość dowolnej,

-cyfrowej liczby

dziesiętnej wyrazi się wzorem:

n-1

n-2

...c

= c

n-1

x p

n-1

+ c

n-2

x p

n-2

+ ... + c

x p

+ c

x p

+ c

x p

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 5

+ 2 x 5

+ 1 x 5

+ 4 x 5

3214

(5)

= 3 x 125 + 2 x 25 + 1 x 5 + 4 x 1

3214

(5)

= 375 + 50 + 5 + 4

3214

(5)

= 434

Architektura Komputera – Kodowanie Liczb

A teraz liczba trójkowa (

= 3,

- {0,1,2} ) 2012

(3)

2012

(3)

= 2 x 3

+ 0 x 3

+ 1 x 3

+ 2 x 3

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

mamy

cyfr

- {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.

n-1

n-2

...c

= c

n-1

+ c

n-2

+ ... + c

+ c

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 2

+ 1 x 2

+ 0 x 2

+ 1 x 2

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.

Architektura Komputera – Kodowanie Liczb

Pierwsze 16 liczb binarnych

0000

x 2

0001

x 2

0010

x 2

0011

x 2

0100

x 2

0101

x 2

0110

x 2

0111

x 2

1000

x 2

1001

x 2

1010

x 2

1011

x 2

1100

x 2

1101

x 2

1110

x 2

Architektura Komputera – Kodowanie Liczb

ZAPAMIĘTAJ

W systemie dwójkowym waga pozycji ma wartość

. Występują tylko dwie cyfry

Wartość liczby obliczamy zgodnie ze wzorem:

n-1

n-2

...c

= c

n-1

+ c

n-2

+ ... + c

+ c

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

= 2

- 1

dla n = 2 mamy 11

(2)

= 3

= 2

- 1

dla n = 3 mamy 111

(2)

= 7

= 2

- 1

dla n = 4 mamy 1111

(2)

= 15 = 2

- 1

Architektura Komputera – Kodowanie Liczb

W każdym przypadku otrzymujemy za górną granicę liczbę równą

- 1

. Podsumujmy:

ZAPAMIĘTAJ

Dla

bitów możemy utworzyć w naturalnym kodzie binarnym liczby z zakresu:

<0, 2

- 1>

Sytuację odwrotną mamy, gdy dana jest określona liczba naturalna

, 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 ≤ 2

- 1

gdzie

jest poszukiwaną liczbą bitów

Liczbę

obliczamy następująco:

n = [log

W + 1]

ZAPAMIĘTAJ

Do zapisu liczby naturalnej

potrzebne jest co najmniej

[log

n + 1]

bitów

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

ósemkowa

wartość

dwójkowa

000

001

010

011

100

101

110

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:

n-1

n-2

...c

= c

n-1

+ c

n-2

+ ... + c

+ c

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

W wyniku otrzymujemy liczbę ósemkową o tej samej wartości:

10111011010101

(2)

. = 27325

(8)

Architektura Komputera – Kodowanie Liczb

Sprawdź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ą:

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ę.

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:

n-1

n-2

...c

= c

n-1

+ c

n-2

+ ... + c

+ c

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

szesnastkowa

wartość

dwójkowa

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

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

1011

0100

1110

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ą:

1111

1101

1010

0111

0011

0010

0000

0001

Zatem

FDA73201

(16)

= 11111101101001110011001000000001

(2)

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 10

+ 5 x 10

+ 3 x 10

+ 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 5

+ 3 x 5

+ 2 x 5

+ 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

+ 2 x

+ 1 x

125

432,331

(5)

= 100 + 15 + 2 +

125

432,331

(5)

= 117

125

432,331

(5)

= 117,688

ZAPAMIĘTAJ

W dowolnym systemie pozycyjnym o podstawie

wartość liczby stałoprzecinkowej obliczamy wg wzoru:

n-1

...c

-1

-2

...c

-m

= c

n-1

+ ... + c

+ c

-1

+ c

-2

+ ... +c

-m

gdzie

- liczba cyfr przed przecinkiem,

- liczba cyfr po przecinku

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 2

+ 1 x 2

+ 0 x 2

+ 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

+ 0 x

+ 1 x

1101,1011

(2)

= 8 + 4 + 1 +

1101,1011

(2)

= 13 +

1101,1011

(2)

= 13,625

Zakres dwójkowych liczb stałoprzecinkowych

Określimy zakres liczb stałoprzecinkowych, w których

bitów przechowuje część całkowitą, a

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

, należących do zbioru {0,1}, to

W - wartość liczby = c

n-1

n-2

...c

-1

-2

...c

-m+1

-m

- wartość części całkowitej = c

n-1

n-2

...c

- wartość części ułamkowej = c

-1

-2

...c

-m+1

-m

W = W

+ W

= c

n-1

+ c

n-2

+ ... + c

+ c

= c

-1

+ c

-2

+ ... + c

-m+1

+ c

-m

Architektura Komputera – Kodowanie Liczb

Zakres części całkowitej

policzyliśmy już wcześniej i wynosi on

<0,2

- 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.

Sprawdźmy ile to będzie dla kolejnych wartości

m = 1, 0,1

= 1 x 2

-1

= 1 x

m = 2, 0,11

= 1 x 2

-1

+ 1 x 2

-2

= 1 x

+ 1 x

m = 3 0,111 = 1 x 2

-1

+ 1 x 2

-2

+ 1 x 2

-3

= 1 x

+ 1 x

Jeśli przyjrzycie się otrzymanym wynikom, to na pewno zauważycie, iż mianownik otrzymanego ułamka ma wartość

, natomiast

licznik jest o 1 mniejszy, czyli

- 1

. Stąd zakres części ułamkowej wynosi:

<0,

Jeśli teraz połączymy zakresy części całkowitej i ułamkowej, to otrzymamy zakres liczby stałoprzecinkowej o

cyfrach całkowitych i

cyfrach ułamkowych, który wynosi:

<0, 2

- 1 +

Architektura Komputera – Kodowanie Liczb

Zadania

. Oblicz wartość następujących liczb:

1234

(5)

, 3456

(7)

, 5678

(9)

. Oblicz wartość następujących liczb binarnych:

110011

(2)

, 1110111

(2)

, 11001110011

(2)

. Jak wzrośnie zakres n bitowej liczby binarnej, jeśli zwiększymy jej długość o 3 bity?

. 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?

. Jak określić liczbę cyfr ósemkowych liczby binarnej zapisanej w systemie szesnastkowym za pomocą n cyfr?

. Oblicz wartość następującej liczby binarnej:

1100111,011101

(2)

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ę

zapisaną w dowolnym systemie pozycyjnym o podstawie

(dla większej ilości

cyfr postępujemy identycznie). Obliczmy wartość liczby wg znanego nam wzoru potęgowego:

= c

+ c

Potęgę

zapiszmy jako

, a

jest równe 1, wobec czego wzór ten przyjmie postać:

= c

+ c

p + c

Wyprowadzamy czynnik

kolejno przed nawiasy:

= (c

+ c

p + c

)p + c

= ((c

+ c

p + c

)p + c

= (((c

p + c

)p + c

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?

Architektura Komputera – Kodowanie Liczb

Wykonując obliczenia w nawiasach:

= c

= w

p + c

= w

p + c

= w

p + c

= w

p + c

- koniec, w

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:

= 0

= w

p + c

= w

p + c

= w

p + c

= w

p + c

= w

p + c

- koniec, w

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.

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 przejdź

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.

0 x 6 +

= 2

2 x 6 +

= 17

17 x 6 +

= 105

105 x 6 +

= 631

631 x 6 +

3790

A teraz sprawdźmy ten wynik normalną metodą przy zastosowaniu wzoru potęgowego:

25314

(6)

= 2 x 6

+ 5 x 6

+ 3 x 6

+ 1 x 6

+ 4 x 6

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

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 przejdź do punktu 2
4.  Jeśli cyfry skończyły się, to zakończ algorytm. Wartość liczby została obliczona.

Architektura Komputera – Kodowanie Liczb

Przykład

Obliczmy opisanym sposobem wartość liczby

11001011011

(2)

= 0

= 0 + 0 +

= 1

= 1 + 1 +

= 3

= 3 + 3 +

= 6

= 6 + 6 +

= 12

= 12 + 12 +

= 25

= 25 + 25 +

= 50

= 50 + 50 +

= 101

= 101 + 101 +

= 203

= 203 + 203 +

= 406

= 406 + 406 +

= 813

= 813 + 813 +

1627

Architektura Komputera – Kodowanie Liczb

Algorytm Hornera dla liczb stałoprzecinkowych

Jeśli mamy daną liczbę stałoprzecinkową zapisaną w postaci

cyfr części całkowitej i

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

Przykład

Obliczmy tą metodą wartość liczby siódemkowej 52,354

(7)

n = 2, m = 3

= 0

= 0 x 7 + 5 = 5

= 5 x 7 + 2 = 37

= 37 x 7 + 3 = 262

= 262 x 7 + 5 = 1839

= 1839 x 7 + 4 = 12877

- ostatnia cyfra, kończymy

Wynik dzielimy przez

= 7

= 343

1287

186

343

Architektura Komputera – Kodowanie Liczb

Sprawdźmy otrzymany wynik za pomocą tradycyjnej metody obliczania wartości liczby stałoprzecinkowej:

52,354

(7)

= 5 x 7

+ 2 x 7

+ 3 x 7

-1

+ 5 x 7

-2

+ 4 x 7

-3

52,354

(7)

= 5 x 7 + 2 x 1 + 3 x

+ 5 x

+ 4 x

343

52,354

(7)

= 35 + 2 +

343

52,354

(7)

= 37 +

147

343

52,354

(7)

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

Architektura Komputera – Kodowanie Liczb

Przeliczanie liczb na dowolny system pozycyjny

Rozważmy następujący problem: mamy liczbę dziesiętną o wartości

. Chcemy znaleźć kolejne cyfry

n-1

n-2

...c

zapisu tej liczby w systemie pozycyjnym o podstawie

. Zapiszmy:

W = c

n-1

+ c

n-2

+ ... + c

+ c

p + c

Podzielmy wartość

przez

. Otrzymamy wtedy:

= c

n-1

n-2

+ c

n-2

n-3

+ ... + c

p + c

Ponieważ wartość każdej cyfry jest zawsze mniejsza od podstawy systemu liczbowego, ułamek

/ p

jest ułamkiem

właściwym. Wobec tego wartość cyfry

otrzymamy jako resztę z dzielenia

przez

. Za nową wartość

przyjmijmy część całkowitą z dzielenia, czyli

= [

] = c

n-1

n-2

+ c

n-2

n-3

+ ... + c

p +

Zwróćcie uwagę, iż otrzymaliśmy nową wartość, której zapis w systemie o podstawie

składa się z tych samych cyfr

z pominięciem ostatniej

. Możemy teraz znów przeprowadzić identyczną operację i otrzymać kolejną cyfrę

jako resztę z dzielenia

przez

. Za nowe

przyjmujemy część całkowitą z dzielenia

przez

, czyli:

= [

] = c

n-1

n-3

+ c

n-2

+ ... +

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

przez

podstawę

Przykład

Dla przykładu znajdźmy wg opisanej metody cyfry w systemie czwórkowym liczby dziesiętnej

1000

W = 1000

= reszta z dzielenia 1000 przez 4 =

= [1000 : 4) = [250] = 250

= reszta z dzielenia 250 przez 4 =

= [250 : 4] = [62,5] = 62

= reszta z dzielenia 62 przez 4 =

= [62 : 4] = [15,5] = 15

= reszta z dzielenia 15 przez 4 =

= [15 : 4] = [3,75] = 3

= reszta z dzielenia 3 przez 4 =

= [3 : 4] = [0,75] = 0

- kończymy, gdyż wynik wynosi zero.

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. Sprawdźmy rachunkiem, czy otrzymana liczba czwórkowa ma w systemie dziesiętnym
wartość 1000.

33220

(4)

= 3 x 4

+ 3 x 4

+ 2 x 4

+ 0 x 4

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 dowolnym systemie pozycyjnym o podstawie

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.

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.

Architektura Komputera – Kodowanie Liczb

Przykład

Znajdźmy reprezentację binarną liczby

253651

253651 : 2 = 126825

i reszta

126825 : 2 = 63412

i reszta

63412 : 2 = 31706

i reszta

31706 : 2 = 15853

i reszta

15853 : 2 = 7926

i reszta

7926 : 2 =

3963

i reszta

3963 : 2 =

1981

i reszta

1981 : 2 =

990

i reszta

990 : 2 =

495

i reszta

495 : 2 =

247

i reszta

247 : 2 =

123

i reszta

123 : 2 =

i reszta

61 : 2 =

i reszta

30 : 2 =

i reszta

15 : 2 =

i reszta

7 : 2 =

i reszta

3 : 2 =

i reszta

1 : 2 =

i reszta

- koniec, wynik dzielenia równy zero

253651 = 111101111011010011

(2)

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ść

, która w docelowym

systemie pozycyjnym

posiada następujące rozwinięcie:

W = c

n-1

+ ...c

+ c

-1

+ ... +c

-m

gdzie

, i = -m...n-1

są cyframi rozwinięcia w systemie

określa liczbę cyfr części całkowitej, a

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

, aby pozbyć się części ułamkowej:

W x p

= (c

n-1

+ ...c

+ c

-1

+ ... +c

-m

W x p

= c

n-1

+ ...c

+ c

-1

+ ... +c

-m

W x p

= c

n-1

n-1+m

+ ...c

+ c

-1

m-1

+ ... +c

-m

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

nie można przedstawić dokładnie za pomocą

cyfr części

ułamkowej w systemie pozycyjnym

- w takim przypadku zaokrąglamy

do najbliższej liczby całkowitej). Po

wykonaniu mnożenia dokonujemy konwersji na system

. Następnie oddzielamy

ostatnich cyfr. Będzie to część

ułamkowa. Reszta cyfr tworzy część całkowitą.

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 5

= 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 c

2842 : 5 = 568 i reszta c

568 : 5 = 113 i reszta c

113 : 5 =

22 i reszta c

22 : 5 =

4 i reszta c

4 : 5 =

0 i reszta c

- koniec, wynik dzielenia zero

Otrzymaliśmy

423321

. Oddzielamy od końca trzy cyfry (

= 3) części ułamkowej i otrzymujemy ostatecznie:

113,688 = 423,321

(5)

Architektura Komputera – Kodowanie Liczb

ZAPAMIĘTAJ

Aby znaleźć rozwinięcie cyfr w dowolnym systemie pozycyjnym

wartości

z dokładnością do

cyfr po przecinku, należy:

1. Wartość

pomnożyć przez

. Jeśli otrzymamy liczbę całkowitą, to

można przedstawić dokładnie w systemie pozycyjnym

. Jeśli otrzymamy liczbę z częścią ułamkową, to wartości

nie da się przedstawić dokładnie na zadanej liczbie cyfr

ułamkowych w systemie pozycyjnym

. W takim przypadku zaokrąglamy iloczyn do najbliższej liczby całkowitej.

2. Obliczamy kolejne cyfry nowej wartości

3. Rozdzielamy przecinkiem

ostatnich cyfr od reszty otrzymanych cyfr. Jeśli cyfr tych jest mniej niż

, 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 2

= 0,1 x 256 = 25,6

Otrzymaliśmy liczbę ułamkową.

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

13 : 2 = 6

i reszta

6 : 2 = 3

i reszta

3 : 2 = 1

i reszta

1 : 2 = 0

i reszta

- 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

itp.

Architektura Komputera – Kodowanie Liczb

Zadania

. Oblicz za pomocą algorytmu Hornera wartość następujących liczb pozycyjnych:

6243

(8)

, 132211

(4)

, 9FF35

(16)

. Oblicz algorytmem Hornera wartość liczby dwójkowej:

11001110001111000011111

(2)

. Oblicz algorytmem Hornera wartość następujących, pozycyjnych liczb stałoprzecinkowych:

221,1022

(3)

, 412,301

(5)

, 634,1252

(7)

. Przelicz na system szóstkowy następujące liczby dziesiętne:

100, 500, 1000, 10000

. Przelicz na system dwójkowy następujące liczby dziesiętne:

100, 1000, 10000

. 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