Liczby: reprezentacja i prosta arytmetyka

1

Przedmioty prowadzone w ramach

Programu Rozwoju WSFiZ w Białymstoku realizowane są w ramach

Programu Operacyjnego Kapitał Ludzki, Priorytet IV Szkolnictwo wyższe i nauka, Poddziałanie 4.1.1

Wzmocnienie potencjału dydaktycznego uczelni, współfinansowanego ze środków

Europejskiego Funduszu Społecznego (POKL.04.01.01-00-030/08)

2.

Liczby: reprezentacja i prosta arytmetyka

Spis treści

2.

Liczby: reprezentacja i prosta arytmetyka ............................................................................. 1

2.1

Zapisy pozycyjne........................................................................................................... 1

2.2

Konwersje dodatnich liczb całkowitych ......................................................................... 3

2.3

Reprezentacja i konwersje dodatnich liczb ułamkowych ................................................ 5

2.4

Liczby zmiennoprzecinkowe ......................................................................................... 7

2.5

Arytmetyka nieujemnych liczb całkowitych .................................................................. 8

2.6

Reprezentacja i arytmetyka ujemnych liczb całkowitych ............................................... 9

2.1 Zapisy pozycyjne

Nie sposób przecenić problemu sposobu zapisu liczb w systemie komputerowym. Z jednej

strony jest on specyficzny i odbiegający od powszechnie używanego, z drugiej – jest wynikiem
decyzji projektowych, mających olbrzymi wpływ na, w zasadzie, każdy komponent tego
systemu. Ten powszechnie używany system to dziesiętny system pozycyjny. Określenie to
oznacza, że dysponujemy w nim dziesięcioma cyframi, że tzw. podstawa (baza) tego systemu jest
równa 10, oraz że wartość, jaką wnosi dana cyfra do liczby będącej ciągiem cyfr zależy od
pozycji (miejsca) danej cyfry w tym ciągu. System komputerowy zapisuje i prowadzi obliczenia
na liczbach posługując się dwójkowym (binarnym) systemem pozycyjnym. Oznacza to, że
dysponujemy w nim dwoma cyframi, że tzw. podstawa tego systemu jest równa 2, oraz że
wartość, jaką wnosi dana cyfra do liczby będącej ciągiem cyfr zależy od pozycji (miejsca) danej
cyfry w tym ciągu dokładnie w taki sam sposób, jak w dobrze nam znanym systemie
dziesiętnym. Cyfry liczby binarnej (0 i 1) nazywamy bitami.

Można zadać zasadne pytanie o powód, dla którego odstąpiono od używania systemu

dziesiętnego pomimo, że jest on dla ludzi systemem najbardziej naturalnym i praktycznie
jedynym używanym. Otóż z wielu różnych powodów najistotniejszy wydaje się ten, iż do
technicznej realizacji urządzeń pamiętających (albo po prostu pamięci) wykorzystano
powszechność występowania w przyrodzie zjawisk o dwóch stabilnych, wyraźnie rozróżnialnych
stanach: np. przeciwne zwroty namagnesowania domeny magnetycznej, naładowany i
rozładowany kondensator, czy też odbity lub rozproszony strumień światła. Urządzenia
zbudowane na takich zasadach okazały się być bardziej niezawodne i tańsze od urządzeń, w
których liczba takich stanów powinna była wynosić 10 (po to, aby każda cyfra była
reprezentowana oddzielnym, tylko sobie właściwym stanem). Ceną, którą płaci się za stosowanie

Liczby: reprezentacja i prosta arytmetyka

2

opisywanych rozwiązań jest konieczność konwersji binarno – dziesiętnych na styku człowiek –
system komputerowy.

Weźmy dowolną liczbę dziesiętną, np. 6295. Zgodnie z zasadami obowiązującymi dla zapisów

pozycyjnych wartość, którą przypisujemy ciągowi cyfr stanowiących tę liczbę możemy obliczyć
z wzoru:

Numery pozycji cyfr:

3 2 1 0

6295 = (6295)

10

= 6∙10

3

+ 2∙10

2

+ 9∙10

1

+ 5∙10

0

gdzie (6295)

10

oznacza, że 6295 jest liczbą w zapisie dziesiętnym (z bazą 10 lub przy podstawie

10), a wartości potęg bazy wynikają z pozycji cyfr. W ogólności, jeżeli d

n

, d

n-1

, ..., d

1

, d

0

są

kolejnymi cyframi pewnej liczby zapisanej przy podstawie b, to zachodzi następujący związek:

(d

n

d

n-1

... d

i

... d

1

d

0

)

b

= d

n

∙ b

n

+ d

n-1

∙ b

n-1

+... + d

i

∙ b

i

+... + d

1

∙ b

1

+ d

0

∙ b

0

(1)

przy czym

0 ≤ i ≤ n (co oznacza, że liczba ma n+1 cyfr)

(2a)

i

0 ≤ d

i

< b (co oznacza, że cyfry są liczbami nieujemnymi, mniejszymi od bazy) (2b)

Jeżeli przyjmiemy, że baza b = 2, to na mocy (2b) jedyne dwie cyfry, jakie mogą pojawić sie

przy tej podstawie to 0 i 1. Wtedy, zgodnie z wzorem (1) dla przykładowej liczby (100101)

2

zachodzi równość:

(100101)

2

= 1∙2

5

+ 0∙2

4

+ 0∙2

3

+ 1∙2

2

+ 0∙2

1

+ 1∙2

0

=

= 1∙2

5

+ 1∙2

2

+ 1∙2

0

=

= 32 + 4 + 1 =

= 37

Powyższy przykład oraz fakt, że 0 razy dowolna liczba jest równe 0, pozwalają sformułować

wniosek, że wartość liczby binarnej (bo tak nazywać będziemy liczby przy podstawie 2) jest
sumą tych potęg dwóch, które odpowiadają kolejnym jedynkom występującym w liczbie.

Zależność (1) jest ogólna, tzn. prawdziwa dla wszystkich możliwych wartości baz. Tak więc

jeżeli np. weźmiemy bazę 8, to na mocy 2b (patrz wyżej) używać możemy cyfr od 0 do 7 i przy
ich pomocy zapisać liczbę (217)

8

. Jej dziesiętny odpowiednik wynosi:

(217)

8

= 2∙8

2

+ 1∙8

1

+ 7∙8

0

=

= 2∙64 + 8 + 7 =

= 143

Pewien problem rodzi się dla przypadków, w których baza jest większa od 10. Wtedy liczba

cyfr przekracza 10 i tradycyjne (arabskie) cyfry 0-9 nie wystarczają. W praktyce używać
będziemy liczb o bazie 16, tzw. liczb heksadecymalnych, dla których potrzebujemy 16 cyfr.
Przyjęło się, że na oznaczenie pierwszych dziesięciu cyfr używane są cyfry 0 – 9, a następne
oznaczane są kolejnymi literami alfabetu ad A, które oznacza 10, do F, które oznacza 15.
Tradycyjnie też można używać dużych liter albo małych (nie mieszając jednych z drugimi), np.

(3BF)

16

= 3∙16

2

+ B∙16

1

+ F∙16

0

=

= 3∙256 + 11∙16 + 15∙1 =

= 959

Liczby: reprezentacja i prosta arytmetyka

3

2.2

Konwersje dodatnich liczb całkowitych

Z praktycznego punktu widzenia bardzo istotna jest wiedza o tym jak zapisać liczbę w

systemie z bazą b

2

, podczas gdy liczba jest zapisana w systemie z bazą b

1

. W przykładach z

poprzedniego rozdziału wykonywane były konwersje do systemu dziesiętnego, czyli tego, w
którym wygodnie było nam prowadzić obliczenia. I chociaż zaprezentowana tam metoda oparta o
wzór 1 (patrz wyżej) jest prawidłowa, to zazwyczaj używa się metod bardziej wydajnych. Jedną z
nich, znaną jako algorytm Hornera, zaprezentujemy poniżej.

Poszukujemy dziesiętnej wartości x liczby (d

n

d

n-1

..., d

1

d

0

)

b

. Konwersję do systemu, w którym

prowadzi się obliczenia można przeprowadzić stosując następujący algorytm:

x ← d

n

(3)

for i = n -1, ... , 1, 0 do
x ← x ∙ b + d

i

Zastosujmy algorytm (3) do obliczenia dziesiętnego odpowiednika liczby (3BF)

16

. W tym

wypadku n = 2, d

2

= 3, d

1

= B = 11 i d

0

= F = 15. A oto obliczenia:

x ← 3

i = 1

x ← 3 ∙ 16 + 11 = 59

i = 0 x ← 59 ∙ 16 + 15 = 959

Konwersja w drugą stronę wykorzystuje operację dzielenia całkowitego, oznaczaną jako div i

operacji reszty z dzielenia całkowitego, oznaczaną jako mod. Poszukujemy cyfr liczby d

n

d

n-1

...,

d

1

d

0

przy bazie b mając daną jej wartość x w systemie dziesiętnym. Konwersję z systemu, w

którym prowadzone są obliczenia można przeprowadzić stosując następujący algorytm:

y ← x

(4)

i ← 0

do

y ← y div b

d

i

← y mod b

i ← i + 1

while (y ≠ 0)

Zastosujmy algorytm (4) do znalezienia binarnego odpowiednika liczby x=37

y

y div 2

y mod 2

------------------------------------------

37

18

1

18

9

0

9

4

1

4

2

0

2

1

0

1

0

1

↑

Strzałka wskazuje kierunek odczytu cyfr

-------------------------------------------

W efekcie mamy: (37)

10

= (100101)

2

Liczby: reprezentacja i prosta arytmetyka

4

Konwersje liczb binarnych na ich odpowiedniki w systemie ósemkowym (oktalnym) i

szesnastkowym (heksadecymalnym) są przypadkami specjalnymi. Wynika to stąd, że 8 jest tym
dla 2, czym 1000 dla 10 (8 = 2

3

, a 1000 = 10

3

), podobnie 16 = 2

4

, a 10000 = 10

4

. Skoncentrujmy

się na systemie oktalnym (rozumowanie dla heksadecymalnego będzie analogiczne). Liczbę
dziesiętną 65102235 można zapisać następująco:

65102235 = 65 milionów + 102 tysiące + 235 jedności =

= 65∙1000000 + 102∙1000 + 235∙1 =

= 65∙1000

2

+ 102∙1000

1

+ 235∙1000

0

Jest to zapis liczby 65102235 w systemie przy podstawie 1000. Tak więc, gdybyśmy posiadali

1000 cyfr, to dziesiętne ich odpowiedniki dla liczby 65102235 wynosiłyby 65, 102 i 235. Można
je uzyskać bezpośrednio z liczby, jeżeli jej cyfry pogrupuje się po trzy (jest to potęga liczby 10,
która daje 1000: 10

3

= 1000) zaczynając od najmniej znaczącej pozycji tj. od prawej ku lewej

stronie:

65102235 = 65 102 235

Zupełnie analogicznie można konwertować liczby zakodowane binarnie do liczb oktalnych.

Podział liczby na grupy 3-cyfrowe wynika, tak jak poprzednio, z faktu, iż 2

3

= 8.

Wcześniej ustalmy jak wyglądają oktalne odpowiedniki 3-cyfrowych liczb binarnych.

Będziemy ich potrzebowali w ostatniej fazie konwersji.

oktalnie

binarnie

oktalnie

binarnie

0

000

4

100

1

001

5

101

2

010

6

110

3

011

7

111

Spróbujmy wykonać konwersję liczby (10011010110)

2

:

(10011010110)

2

= 010 011 010 110

(binarnie)

2 3 2 6

(oktalnie)

W pierwszej od lewej, tj. ostatniej grupie zabrakło cyfr, toteż dodano na początku zero (co nie

zmieniło wartości reprezentowanej przez tę grupę). W ostatnim wierszu znajdują się oktalne
cyfry, które są odpowiednikami znajdujących się nad nimi dwójkowych grup 3-cyfrowych. Tak
więc finalnie:

(10011010110)

2

= (2326)

8

Zupełnie analogicznie przebiega konwersja binarno – heksadecymalna, przy czym liczbę

binarną dzielimy na grupy 4-cyfrowe (2

4

= 16), a potem wyliczamy ich odpowiedniki

heksadecymalne. Jako przykład weźmy tą samą liczbę, co poprzednio:

(10011010110)

2

= 0100 1101 0110

(binarnie)

4 13 6

(dzisiętnie)

4 D 6

(heksadecymalnie)

(10011010110)

2

= (4D6)

16

Konwersje odwrotne, tj. oktalno-binarna i heksadecymalno-binarna przebiegają dokładnie

odwrotnie. Oznacza to, że każdą cyfrę liczby oktalnej zamieniamy na 3-cyfrową liczbę binarną, a

Liczby: reprezentacja i prosta arytmetyka

5

każdą cyfrę liczby heksadecymalnej zamieniamy na 4-cyfrową liczbę binarną, w obu
przypadkach uzupełniając z lewej strony zerami te z nich, które mają mniej niż odpowiednio 3
lub 4 cyfry (poza pierwszą). Poniższy przykład prezentuje takie konwersje:

(1067)

8

= (1 000 110 111)

2

(2FA)

16

= (10 1111 1010)

2

Konwersję oktalno – heksadecymalną i do niej odwrotną można prowadzić przechodząc przez

konwersję do zapisu binarnego, a z niego do zapisu docelowego.

2.3

Reprezentacja i konwersje dodatnich liczb ułamkowych

Liczba ułamkowa może być traktowana jako suma części całkowitej i ułamkowej. Ponieważ

problematykę reprezentacji i konwersji liczb całkowitych została omówiona w poprzednim
rozdziale to tu skupimy się wyłącznie na ułamkach. Pozwala nam na to taka własność zapisów
pozycyjnych, zgodnie z którą zapis liczby ułamkowej może być potraktowany jako złożenie
zapisu jej części całkowitej, separatora w postaci kropki oraz zapisu części ułamkowej. Własność
ta znajduje też potwierdzenie w arytmetyce: liczba ułamkowa jest sumą swojej części całkowitej i
ułamkowej, np. 25.583 = 25 + 0.583.

Zacznijmy od odpowiednika równania 1 (patrz wyżej) dla liczb l z zakresu 0<l<1. W

ogólności, jeżeli 0.d

1

, d

2

, ..., d

n-1

, d

n

są kolejnymi cyframi pewnego ułamka zapisanego przy

podstawie b, to zachodzi następujący związek:
(0.d

1

d

2

... d

i

... d

-(n-1)

d

n

)

b

= d

1

∙ b

-1

+ d

2

∙ b

-2

+ ... + d

i

∙ b

-i

+ ... + d

n-1

∙ b

-(n-1)

+ d

n

∙ b

-n

(5)

przy czym

0 < i < n (co oznacza, że liczba ma n+1 cyfr)

(5a)

i
0 < d

i

< b (co oznacza, że cyfry są liczbami nieujemnymi, mniejszymi od bazy)

(5b)

Weźmy zapis dziesiętny (baza b = 10) i sprawdźmy prawdziwość wzoru (5) na przykładzie

ułamka 0.7395. Mamy:

(0.7395)

10

= 7∙10

-1

+ 3∙ 10

-2

+ 9∙ 10

-3

+ 5∙ 10

-4

co jest dla nas, przyzwyczajonych do zapisów dziesiętnych truizmem. Dla zapisów binarnych
(baza b=2) obowiązują analogiczne zależności, np.:

(0.1101)

2

= 1∙2

-1

+ 1∙2

-2

+ 0∙2

-3

+ 1∙2

-4

=

= 2

-1

+ 2

-2

+ 2

-4

=

= 0.5 + 0.25 + 0.0625 =

= 0.8125

Jak widać, tak jak to było dla liczb całkowitych, wartość ułamka binarnego jest sumą tych

potęg dwóch, które odpowiadają kolejnym jedynkom występującym w ułamku.

Wzór (5) pozwala obliczać dziesiętną wartość ułamka binarnego. Do kompletu potrzebujemy

procedury odwrotnej, tj. procedury znajdowania reprezentacji binarnej zadanego ułamka
dziesiętnego. Będzie to zmodyfikowana wersja procedury 4 (patrz wyżej):

y ← x

(5)

i ← 1
do

Liczby: reprezentacja i prosta arytmetyka

6

wrk = y * 2
d

i

← trunc ( wrk )

y ← wrk - d

i

i ← i + 1

while (y ≠ 0)

W powyższym zapisie wykorzystano funkcję trunc(x), która obcina część ułamkową liczby x.

Z powyższych zapisów wynika, że kolejne bity binarnego ułamka są częścią całkowitą
podwojonej, aktualnej wartości ułamka (d

i

← trunc (y * 2)). Obliczenia kończą sie w momencie,

w którym część ułamkowa tego podwojenia jest zerem.

Wykorzystajmy algorytm (5) i przeprowadźmy konwersję ułamka dziesiętnego uzyskanego

jako rezultat w poprzednim przykładzie.

wrk

d

i

y

0.8125 * 2 =

1 ↓ 0.6250

0.625 * 2 =

1

0.25

0.25 * 2 =

0

0.5

0.5 * 2 =

1

0

Strzałka wskazuje kierunek odczytywania bitów (zaczynając od najbardziej znaczącego).

O ile konwersja dziesiętno – binarna dla liczb całkowitych zawsze daje skończoną

reprezentację konwertowanej liczby (tzn. ilość bitów uzyskanych w procedurze konwersji jest
skończona), to procedura konwersji ułamka dziesiętnego o skończonej liczbie cyfr może
prowadzić do nieskończonej liczby bitów, o czym świadczy kolejny przykład. Spróbujmy
przekonwertować ułamek 0.3:

wrk

d

i

y

0.3 * 2 =

0 ↓ 0.6

0.6 * 2 =

1

0.2

0.2 * 2 =

0

0.4

0.4 * 2 =

0

0.8

0.8 * 2 =

1

0.6

0.6 * 2 =

1

0.2

0.2 * 2 =

0

0.4

0.4 * 2 =

0

0.8

....

Jak widać, osiągane bity i reszty zaczynają się powtarzać i proces ten nie ma końca. Osiągnięty

rezultat zapisujemy w następujący sposób:

(0.3)

10

= (0.01 0011 0011 ...)

2

= 0.01 (0011)...

Zapis (0011) użyty w prawej stronie równości oznacza, że w rozwinięciu binarnym ułamka 0.3
ciąg bitów 0011 powtarza się okresowo do nieskończoności.

Na zakończenie tej części zapiszmy binarny odpowiednik liczby 37.8125. Ponieważ

37 = (100101)

2

oraz 0.8125 = (0.1101)

2

to

37.8125 = (100101.1101)

2

Liczby: reprezentacja i prosta arytmetyka

7

2.4 Liczby zmiennoprzecinkowe

W wielu dziedzinach ludzkiej aktywności istnieje konieczność prowadzenia obliczeń

jednocześnie na bardzo małych i na bardzo dużych liczbach. Podobnie skrajne są wymagania
odnośnie ilości uwzględnianych w liczbach cyfr. Sposobem pozwalającym kontrolować
istniejące w związku z takimi wymaganiami problemy jest koncepcja zapisu
zmiennoprzecinkowego. Koncepcja ta, najprościej mówiąc, polega na tym, że zamiast używać
zapisów takich jak ten:

29784678367.478920

lub ten

0.0000000004958372

używać w ich miejsce zapisów następujących:

0.2978557836747892∙10

11

i odpowiednio

0.4958372∙10

-9

Jeżeli potęgi są tak dobrane, że liczba przed potęgą ma zerową część całkowitą i pierwsza cyfra

ułamka jest różna od zera, to mówimy, że liczby te maja postać znormalizowaną. Ułamek w
takich liczbach jest nazywany mantysą, wykładnik potęgi – cechą, a liczba potęgowana – bazą. O
liczbie cyfr występujących w ułamku przed potęgą (w matysie) mówimy jako o tzw. liczbie cyfr
znaczących. Jeżeli ilość cyfr znaczących przewyższa liczbę dostępnych na te cyfry miejsc, to
ułamek obcinamy tak, aby liczba miejsc była równa liczbie cyfr. Przy tej operacji ostatnia
(najmniej znacząca) cyfra ulega zaokrągleniu zgodnie z ogólnie znanymi zasadami
konstruowania zaokrągleń. Jeżeli natomiast liczba cyfr znaczących jest za mała w stosunku do
liczby miejsc, to wolne miejsca wypełnia się zerami. I tak, jeżeli w podanym wcześniej
przykładzie liczbę miejsc znaczących przyjąć 4, to liczby te byłyby zapisane następująco:

0.29786∙10

11

i odpowiednio

0.4958∙10

-9

Typowy sposób przechowywanie liczby zmiennoprzecinkowej w pamięci komputera polega na

wydzieleniu w obrębie pewnej określonej liczby bajtów (za chwilę wyjaśnimy dokładniej słowa
„pewnej określonej liczby”) oddzielnego obszaru na cechę (czyli wykładnik), mantysę (czyli
ułamek) i znak liczby. Baza dla zapisów komputerowych jest oczywiście równa 2. Znak
pamiętany jest na jednym bicie i nie musi to być pierwszy bit obszaru. W obszarze mantysy
pamiętane są wyłącznie cyfry znaczące – nie ma sensu pamiętać 0 i kropki dziesiętnej w sytuacji,
w której zakłada się, że liczby zawsze przechowywane są w postaci znormalizowanej.

Wróćmy na chwilę do słów „pewna określona liczba” bajtów. Otóż jest oczywiste, że im

większe i dokładniejsze liczby chcemy przechowywać tym więcej miejsca musimy przewidzieć
na cyfry cechy i mantysy. Ponieważ potrzeby użytkowników są pod tym względem bardzo
zróżnicowane, to zazwyczaj projektanci oferują kilka różnych typów organizacji obszarów
służących do przechowywania liczb zmiennoprzecinkowych tak, aby użytkownik mógł wybrać
ten, który najlepiej pasuje do jego potrzeb. Na rysunku poniżej pokazane są 4 przykładowe typy
organizacji takich obszarów nazwane typami F, D, G i H.

Typ F

Typ D

15 14

7 6 0

15 14

7 6 0

Z

Cecha Mantysa

Z

Cecha Mantysa

Mantysa

Mantysa

31

16

Mantysa

Mantysa

63

48

Liczby: reprezentacja i prosta arytmetyka

8

Typ G

Typ H

15 14

4 3 0

15 14

0

Z

Cecha Mant.

Z

Cecha

Mantysa

Mantysa

Mantysa

Mantysa

16

Mantysa

.........

bajtów

63

48

Mantysa

Mantysa

127

112

Literowe nazwy typów nie są znormalizowane i chociaż te użyte w przykładzie pochodzą z

konkretnego modelu komputera to powinny być traktowane jako przykładowe.

Na rysunkach powyżej podano numery niektórych istotnych dla organizacji zapisu bitów.

Organizacja wszystkich typów oparta jest o 2-bajtowy ciąg bitów (często nazywany słowem). Jak
widać z rysunku bit znaku (oznaczony przez Z) pamiętany jest dla każdego typu w ostatnim (15)
bicie pierwszego słowa. Dla typów F i D na cechę (wykładnik) przeznaczonych jest 8 bitów. Na
reszcie bitów zapisana jest mantysa, przy czym kolejne bity pamiętane są w kolejności
wynikającej z numerów bitów zamieszczonych na rysunku. Ciekawe jest, że typ D pamiętany jest
na tej samej liczbie słów (4) co typ G. Organizacja wewnętrzna tych typów jest jednak różna: w
typie D na cechę przeznaczono 8, a w typie G – 11 bitów. W związku z tym liczba bitów mantysy
dla tych typów jest odpowiednio 55 i 52. Najwięcej – bo aż 8 słów zajmuje typ H. Cecha
pamiętana jest w nim na 15 bitach, a mantysa – na 112.

W tabeli poniżej podano jak liczby bitów dla cechy i mantysy dla poszczególnych typów

przekładają się na zakresy pamiętanych liczb i liczby cyfr znaczących w zapisie dziesiętnym.

Typ

Rozmiar

Zakres

Liczba cyfr

(bajty)

dziesiętnych

F

4

29∙10

-38

↔ 1.7∙10

38

7

D

8

29∙10

-38

↔ 1.7∙10

38

16

G

8

0.56∙10

-308

↔ 0.9∙10

-308

15

H

16 0.84∙10

-4932

↔ 0.59∙10

4932

33

Arytmetyka na liczbach zmiennoprzecinkowych nie będzie omawiana. Ograniczymy się do

informacji, że generalnie składa się ona z czterech faz: odczytania argumentów (przy opisanej
organizacji przechowywania liczb jest to krok konieczny i nie trywialny), przeprowadzenia
obliczeń, normalizacji wyniku i zapisania go zgodnie z organizacją żądanego typu wynikowego.

2.5

Arytmetyka nieujemnych liczb całkowitych

W dziedzinie nieujemnych liczb binarnych działania dodawania i mnożenia łatwo jest

zdefiniować przez podanie wyników tych działań dla wszystkich możliwych kombinacji wartości
argumentów. Na rysunku 2.1 (patrz niżej) pokazane są tabele definiujące te działania.

Liczby: reprezentacja i prosta arytmetyka

9

a)

b)

(+)

2

0

1

0

0

1

1

1

10

Rysunek 2.1. Binarne dodawanie i mnożenie.

Powyższe definicje zostaną wykorzystane w przykładach prezentujących obliczenia niezbędne

przy wykonywaniu działań dodawania i mnożenia. Zasady są analogiczne do tych
wykorzystywanych przy działaniach na liczbach dziesiętnych. W szczególności chodzi tu o tzw.
przeniesienie. Na rysunku 2.1 a) widać, że 1 + 1 = 10

2

, co oznacza, że jeżeli dodajemy dwie

jedynki występujące na i-tej pozycji (licząc od prawej do lewej) w dodawanych, wielocyfrowych
liczbach binarnych, to na i-tej pozycji wynik będzie 0, a jedynka z pary 10

2

zostanie przeniesiona

na pozycję i+1 i tam dodana. A oto przykłady, w których dla kontroli, obok wersji binarnej
prezentowana będzie wersja dziesiętna. Dla ułatwienia percepcji w dalszej części tekstu ciągi zer
i jedynek będą grupowane po 4 ze spacją separującą. Zaczniemy od dodawania:

binarnie

dziesiętnie

1110 1010

234

+ 110 1001

+105

10101 0011

339

A teraz mnożenie wykonywane dokładnie w ten sam sposób jak dla liczb dziesiętnych:

binarnie

dziesiętnie

1011

11

*1101

*13

1011

33

0 000

11

10 11

101 1

1000 1111

143

Działania na liczbach w zapisach oktalnym i heksadecymalnym są najczęściej wykonywane po

ich uprzedniej konwersji do postaci binarnej.

2.6 Reprezentacja i arytmetyka ujemnych liczb

całkowitych

Kod, którego do tego momentu używaliśmy do zapisu całkowitych, nieujemnych liczb

binarnych nosi nazwę naturalnego kodu binarnego (NKB). Kod NKB stanowi doskonałą bazę
wyjściową do prowadzenia rozważań dotyczących działań na liczbach, ale nie obejmuje wielu
bardzo istotnych, chociażby z punktu widzenia zastosowań, zbiorów liczb, w tym liczb
ujemnych.

Najczęściej do reprezentowania całkowitych liczb ujemnych używany jest jeden z trzech

kodów:

1. Znak / moduł (ZM);
2. Kod uzupełnień do 1 (U1);
3. Kod uzupełnień do 2 (U2).

(*)

2

0

1

0

0

0

1

0

1

Liczby: reprezentacja i prosta arytmetyka

10

Każdy z wymienionych kodów ma tą własność, że zapisane w nim liczby dodatnie są tożsame

z liczbami zapisanymi w kodzie NKB. Również w każdym z nich pierwszy (licząc od lewej) bit
liczby używany jest jako bit znaku. Konsekwencją tego faktu jest to, że w arytmetyce liczb
ujemnych musimy z góry ustalić liczbę bitów liczby, aby w sposób jednoznaczny rozróżniać bit
znaku od pozostałych bitów.

W kodzie ZM pierwszy, tj. najbardziej znaczący bit reprezentuje znak nie wnosząc do liczby

wartości związanej ze swoją pozycją. Z n bitów użytych w tym kodzie do zapisu liczby, do
zapisu jej modułu (w kodzie NKB) użytych jest n -1 bitów, a 1 bit do zapisu znaku. Jego wartość
0 oznacza znak +, a 1 oznacza znak –. Np. dla zapisów 8-bitowych mamy:

37 = (0010 0101)

ZM

↑

–37 = (1010 0101)

ZM

↑

bit znaku

Konsekwencją przyjętych definicji jest podwójna reprezentacja zera: np. dla 8-bitowych liczb

mamy:

0 = (0000 0000)

ZM

oraz

0 = (1000 0000)

ZM

Arytmetyka na liczbach w kodzie ZM sprowadza się do dwóch kroków:

1. Ustalenie znaku wyniku;
2. Przeprowadzenia działania na modułach argumentów.

Pierwszy krok może wymagać porównania modułów argumentów (np. przy odejmowaniu).

Drugi – jest działaniem na liczbach w kodzie NKB. Reasumując: arytmetyka na liczbach ZM
wymaga dodatkowych (chociaż prostych) operacji dodatkowych.

Główną zaletą kodu ZM jest jego prostota. Głównymi wadami – podwójna reprezentacja 0 i

niejednorodność znaczenia bitów zakodowanej w nim liczby (przez swą odmienność bit znaku
nie może być traktowany tak jak pozostałe bity). Ta ostatnia cecha komplikuje algorytmy działań,
a co za tym idzie konstrukcję realizujących je układów elektronicznych.

W kodzie uzupełnień do 1 (U1), tak jak w kodzie ZM pierwszego (od lewej) bitu używa się

jako bitu znaku. Wartość tego bitu równa 0 oznacza liczbę dodatnią i w takim przypadku
pozostałe bity kodują liczbę w kodzie NKB, czyli dokładnie tak samo jak w kodzie ZM. Jego
wartość równa 1 oznacza liczbę ujemną, a wtedy pozostałe bity reprezentują liczbę w taki
sposób, że ich negacja (tzn.: 0→1 i 1→0) daje moduł kodowanej liczby. Np.

37 = (0010 0101)

U1

i

–37 = (1101 1010)

U1

Z przytoczonej definicji wynika, że aby otrzymać liczbę ujemną w kodzie U1 wystarczy

zanegować wszystkie bity modułu tej liczby. Ponieważ zamiana każdego 0 na 1 i każdej 1 na 0
może być interpretowana jako zastąpienie każdego bitu wartością, która uzupełnia wejściową
wartość tego bitu do wartości 1, to dało to asumpt do nazwania kodu kodem uzupełnień do 1. Tak
jak w kodzie ZM kod U1 ma podwójna reprezentację 0:

Liczby: reprezentacja i prosta arytmetyka

11

0 = (0000 0000)

U1

oraz

0 = (1111 1111)

U1

Aby opisać problemy związane a prowadzeniem arytmetyki na liczbach w kodzie U1 opiszemy

procedurę dodawania i odejmowania. Algorytm przeprowadzenia tych działań polega na
zastosowaniu zwykłego dodawania tak, jak gdybyśmy mieli do czynienia z liczbami w kodzie
NKB oraz dodatkowo na zastosowaniu tzw. przeniesienia cyklicznego (ang. end-arround carry).
Polega ono na dodaniu do uzyskanej sumy bitu, który jest bitem przeniesienia z dodania
najbardziej znaczących bitów liczb (tj. pierwszych od lewej). A oto przykład. Na jego potrzeby
załóżmy, że posługujemy się zapisami 5-cio bitowymi:

Dziesiętnie Binarnie Dziesiętnie Binarnie Dziesiętnie Binarnie

Dziesiętnie Binarnie

+3 = 00011

+3 = 00011

−3 = 11100

−3 = 11100

+6 = +00110

−6 = +11001

+6 = +00110

−6 = +11001

001001

011100

100010

110101

+0

+0

+1

+1

+9 = 01001

−3 = 11100

+3 = 00011

−9 =

10110

Rysunek 2.2. Przykład dodawania wykorzystującego przeniesienie cykliczne w arytmetyce U1.

Zauważmy, że przy technice dodawania zaprezentowanej w powyższym przykładzie

odejmowanie sprowadziło się do zwykłego dodawania. Niestety dodawanie takie nie jest zbyt
efektywne. Po pierwsze musimy wykonać dwa dodawania: najpierw dodajemy argumenty, a
następnie bit przeniesienia cyklicznego. Ponadto jeżeli założyć, że dodanie pojedynczego bitu
trwa czas ∆t, to dodanie n bitowych liczb trwa co najmniej (n+1)∆t, gdyż wartość bitu
przeniesienia cyklicznego znana jest dopiero po dodaniu wszystkich n bitów liczb.

Idea kodów uzupełnień do bazy zapisu liczb (np. uzupełnień do 2 dla liczb binarnych) jest

dosyć stara i jeżeli wierzyć przekazom, pochodzi z czasów, kiedy dodawano liczby przy pomocy
mechanicznych maszynek na korbkę. Liczba cyfr w dodawanych liczbach była w nich
limitowana ilością bębnów z nadrukowanymi cyframi (każdy bęben miał na swojej powierzchni
10 cyfr od 0 do 9). Obudowa przesłaniała bęben w taki sposób, że użytkownik przez prostokątny
otwór widział tylko jedną cyfrę. Rząd bębnów, jeden obok drugiego, pozwalał nastawić liczbę w
taki sposób, w jaki nastawiamy kod w cyfrowym zamku teczki lub walizki. Kręcąc korbką można
było uzyskać sumę dwóch kolejno nastawianych argumentów. Opisywane maszynki pozwalały
wyłącznie dodawać, a potrzeby życia sprawiały, że poszukiwano sposobu wykorzystania ich do
odejmowania. Sposób, jakiego się dopracowano pokazany będzie w kolejnym przykładzie.
Załóżmy, że potrzebujemy wykonać następujące odejmowanie na maszynce o 8 bębnach:

14 596 187

− 2 532 172

Pomysł polegał na tym, że zamiast odejmować liczbę 2 532 172, to zastępowano ją różnicą

100000000 i 2 532 172, którą to różnicę obliczano w pamięci, a uzyskany wynik dodawano do
14 596 187 wykorzystując maszynkę liczącą. Zanim sprawdzimy efekt opisanej metody
zauważmy, że 100000000 = 10

8

, a więc potęga jest równa maksymalnej ilości cyfr liczb, które

można było dodawać w naszej maszynce. A oto obliczenia:

Liczby: reprezentacja i prosta arytmetyka

12

100 000 000

− 2 532 172

97 467 828 = − 2 532 172 + 100 000 000

+ 14 596 187 = [phone]

112 064 015 = 12 064 015 + 100 000 000

Ponieważ maszynka miała tylko 8 bębnów i 8 otworów do pokazywania cyfr wyniku to

pierwsza z lewej jedynka musiała być pominięta i maszynka pokazywała prawidłowy wynik, tj.
12064015. Liczbę 97 467 828 nazywamy uzupełnieniem do 10 liczby 2 532 172.

Do konstrukcji kodu uzupełnień do 2 (U2) wykorzystano pomysł opisany w powyższym

przykładzie. Uzupełnień do 2, a nie do 10, bo dla zapisów binarnych liczba 2 jest podstawą
kodowania. Spróbujmy znaleźć uzupełnienie do 2 dla liczby 37 przy założeniu, że używać
będziemy zapisów 8-bitowych. Aby to osiągnąć, należy, tak jak to pokazano w przykładzie, odjąć
od 2

8

liczbę 37 zapisaną na 8 bitach:

2

8

= (1 0000 0000)

2

−(37) = − (0010 0101)

2

−37 =

(1101 1011)

U2

Powyższe odejmowanie zostało przeprowadzone analogicznie do klasycznego, tj. dziesiętnego.

Zacznijmy od pierwszych cyfr od prawej: aby odjąć 1 od 0 należy wziąć pożyczkę z poprzedniej
pozycji. Ponieważ wszystkie 8 poprzedzających cyfr to zera, pożyczka będzie zrealizowana z
pierwszej w liczbie jedynki. Gdyby to było kodowanie dziesiętne, to pożyczka wynosiłaby 10, a
reszta pożyczki rozłożyłaby sie w ten sposób, że na wszystkich pozycjach poprzedzających
byłyby cyfry 9 (czyli największe cyfry w tym kodowaniu). Pierwsza w liczbie jedynka znikłaby,
bo została zamieniona na pożyczkę.

Przy zapisach binarnych pożyczka na pierwszej pozycji (od prawej) wynosi 2, bo tyle wynosi

baza w kodowaniu binarnym, a na wszystkich pozycjach poprzedzających pożyczka spowoduje
pojawienie się maksymalnej cyfry w zapisie binarnym, tj. jedynki. Pierwsza jedynka zniknie, bo
to z niej została zrealizowana pożyczka. Tak więc w rezultacie mamy odjąć następujące liczby:

1111 1112

− 0010 0101

1101 1011

Końcowy rezultat zapisany w rzędzie po kreską jest teraz oczywisty.

W praktyce, w celu uzyskania kodu U2 dowolnej liczby wykonanie wszystkich opisanych

działań nie jest konieczne. Istnieje bowiem prosta metoda prowadząca do tego samego rezultatu.
Sprowadza się ona do wykonania 2 kroków, w których należy:

1. zamienić zera na jedynki i jedynki na zera (czyli znaleźć kod U1 dla konwertowanej liczby);
2. dodać do otrzymanego rezultatu 1.
Spróbujmy ponownie z liczbą 37 zapisaną na 8 bitach:

37 = (0010 0101)

2

(1101 1010)

2

+

1

−37 = (1101 1011)

U2

Porównując otrzymany rezultat z wynikiem uzyskanym w sposób formalny widać, że opisana

metoda działa prawidłowo. Warto zauważyć, że jeżeli do liczby ujemnej zapisanej w kodzie U2
zastosujemy jeszcze raz procedurę obliczenia kodu U2, to w rezultacie otrzymamy pierwotną
liczbę dodatnią. Sprawdźmy:

Liczby: reprezentacja i prosta arytmetyka

13

−37 = (1101 1011)

U2

0010 0100

+

1

+37 = (0010 0101)

2

Wykorzystajmy nabytą widzę i przeprowadźmy obliczenia analogiczne do tych,

zaprezentowanych na rysunku 2.2 (patrz wyżej), ale tym razem stosując kod U2.

Ponieważ w przykładzie będą między innymi potrzebne liczby −3 i −6 to zaczniemy od

wyliczenia dla nich kodów U2 pamiętając, że działamy na zapisach 5cio bitowych:

3 =

(00011)

2

6 =

(00110)

2

(11100)

2

(11001)

2

+

1

+

1

−3 = (11101)

U2

−6 = (11010)

U2

Dziesietnie

Binarnie Dziesiętnie Binarnie Dziesiętnie Binarnie

Dziesiętnie Binarnie

+3 =

00011

+3 = 00011

−3 = 11101

−3 = 11101

+6 =

+00110

−6 = +11010

+6 = +00110

−6 = +11010

+9 = 01001

−3 = 11101

100011

110111

00010

+3 = 00011

−9 =

01000

+

1

+ 1

+3 = 00011

+9 =

01001

Rysunek 2.3. Przykład dodawania w arytmetyce U2.

Pierwsze 2 kolumny to klasyczne dodawanie w kodzie NKB, które nie wymaga komentarza. W

kolumnie Binarnie drugiej pary kolumn pierwsze od góry dodawanie dało 11101. Jedynka na
początku świadczy, że jest to liczba ujemna. Zakładając, że jest to zapis U2 sprawdzamy jej
wartość zamieniając bity na przeciwne i dodając 1. Dwie kolejne kolumny pokazują sytuację
bardzo podobną do poprzedniej, ale jak widać wynik dodawania jest 6-cio bitowy. Postępowanie
w takim przypadku jest analogiczne do tego, dotyczącego maszynki liczącej, w którym
pokazaliśmy, że odrzucenie cyfry będącej wynikiem niezerowego przeniesienia z dodawania
najbardziej znaczących cyfr zagwarantowało poprawny wynik. Podobnie i tutaj, gdzie pierwsza
jedynka w zapisie wynikowym została pominięta. Ostatnia para kolumn pokazuje sytuację
odejmowania liczby ujemnej od ujemnej. Ponieważ −3 − 6 = −3 + (−6) to możemy zastosować
schemat postępowania analogiczny jak dla przypadku +3 − 6.

Poniżej podana jest lista właściwości kodu U2. Niektóre z nich są uogólnieniami

dotychczasowych rozważań. Inne będą wyjaśnione w dalszej części tekstu.

1. Liczby dodatnie mają 0 na pierwszym bicie i łącznie z pozostałymi bitami są zapisane tak, jak

liczby w kodzie NKB;

2. Liczby ujemne mają 1 na pierwszym bicie (od lewej) i to je odróżnia od liczb dodatnich;
3. Pozostałe bity liczb ujemnych powstają przez zanegowanie wszystkich bitów i dodanie

jedności;

4. Istnieje tylko jedna reprezentacja zera składająca się z ciągu samych zer;
5. Dla zapisów n bitowych najmniejsza możliwa wartość wynosi -2

n-1

, a największa wartość to

(2

n-1

–1);

6. Ze względu na to, że dla dwóch dowolnych liczb a i b zachodzi równość: a – b = a + (–b), to

odejmowanie liczby można sprowadzić do dodania jej kodu U2;

7. Kod U2 kodu U2 dowolnej liczby daje w rezultacie oryginalną liczbę.

Liczby: reprezentacja i prosta arytmetyka

14

8. Jeżeli w rezultacie prowadzonego dodawania pojawi się przeniesienie na najbardziej

znaczącym bicie, to bit taki ignorujemy.

Co do punktu 4, to 0 nie jest liczbą ujemną, a więc powinno być zapisywane zgodnie z kodem

NKB. Zauważmy, że liczba, która ma jedynkę na pierwszej pozycji, a potem same zera nie jest
zerem, o czym można przekonać się stosując do niej powtórnie kodowanie U2. To postępowanie
pokazuje również, że jest to najmniejsza z liczb w kodzie U2, jaką można zapisać na n bitach
(patrz punkt 5). Jest tak, ponieważ po odwróceniu bitów w liczbie będą same jedynki, czyli
największa możliwa liczba odwrotna. Stąd też największa liczba zapisana na n bitach ma na
początku 0, a dalej same jedynki. Liczba taka jest równa 2

n-1

–1.

Na koniec zastanówmy się, czy w wyniku dodawania lub odejmowania dowolnych liczb n-

bitowych w kodziU2 może dojść do sytuacji, w której wynik operacji uzyskany za pomocą
opisanych algorytmów nie jest prawidłowy. Łatwo jest podać przykłady wskazujące, że takie
sytuacje są możliwe. Oto dwa z nich, w których na 5-cio bitowych liczbach należących do
przedziału legalnych liczb (dla 5-ciu bitów jest to: minimalna liczba = –2

5-1

= –16; maksymalna

liczba = 2

5-1

–1 = 15) uzyskano wyniki spoza tego przedziału.

a)

Dziesiętnie

U2

b) Dziesiętnie U2

(+10)

10

= 01010

(−10)

10

=

10110

(+8)

10

= +01000

(−8)

10

=

+11000

(+18)

10

≠ 10010 = (−14)

10

(−18)

10

≠

01110 = (14)

10

Fakt, iż osiągnięte wyniki są złe jest oczywisty już na pierwszy rzut oka, a to z tego powodu, że

znaki wyników są sprzeczne ze znakami argumentów: w przykładzie a) dodajemy liczby
dodatnie, a wynik ma znak minus, w przykładzie b) – odwrotnie.

Powyższe sytuacje nazywane są nadmiarem. Należy zwrócić uwagę, że są one jakościowo

różne od tych, w których jako efekt wykonania działania występowało niezerowe przeniesienie z
najstarszych pozycji, a które finalnie było ignorowane. Występowanie nadmiaru nie jest jakąś
szczególną cechą kodu U2 – występuje on także jako efekt wykonywania operacji
arytmetycznych na liczbach zapisanych w innych kodach. W związku z tym problem polega na
tym, ile kosztuje wykrycie, że taka sytuacja ma miejsce. W jednym z następnych rozdziałów
pokażemy, ze układy elektroniczne wykrywające nadmiar w działaniach prowadzonych na
liczbach w kodzie U2 mogą być zrealizowane w banalnie prosty sposób.