Liczby: reprezentacja i prosta arytmetyka
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, wyraz
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
1
Liczby: reprezentacja i prosta arytmetyka
opisywanych rozwiązań jest konieczność konwersji binarno  dziesiętnych na styku człowiek 
system komputerowy.
Wez
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"103 + 2"102 + 9"101 + 5"100
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 dn, dn-1, ..., d1, d0 są
kolejnymi cyframi pewnej liczby zapisanej przy podstawie b, to zachodzi następujący związek:
(dndn-1 ... di ... d1d0)b = dn" bn + dn-1" bn-1 +... + di" bi +... + d1 " b1 + d0 " b0 (1)
przy czym
0 d" i d" n (co oznacza, że liczba ma n+1 cyfr) (2a)
i
0 d" di < 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"25 + 0"24 + 0"23 + 1"22 + 0"21 + 1"20 =
= 1"25 + 1"22 + 1"20 =
= 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. wez
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"82 + 1"81 + 7"80 =
= 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"162 + B"161 + F"160 =
= 3"256 + 11"16 + 15"1 =
= 959
2
Liczby: reprezentacja i prosta arytmetyka
2.2 Konwersje dodatnich liczb całkowitych
Z praktycznego punktu widzenia bardzo istotna jest wiedza o tym jak zapisać liczbę w
systemie z bazą b2, podczas gdy liczba jest zapisana w systemie z bazą b1. 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 (dndn-1 ..., d1d0)b. Konwersję do systemu, w którym
prowadzi się obliczenia można przeprowadzić stosując następujący algorytm:
x �! dn (3)
for i = n -1, ... , 1, 0 do
x �! x " b + di
Zastosujmy algorytm (3) do obliczenia dziesiętnego odpowiednika liczby (3BF)16. W tym
wypadku n = 2, d2 = 3, d1 = B = 11 i d0 = 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 dndn-1 ...,
d1d0 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
di �! 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
3
Liczby: reprezentacja i prosta arytmetyka
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 = 23, a 1000 = 103), podobnie 16 = 24, a 10000 = 104. 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"10002 + 102"10001 + 235"10000
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: 103 = 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ż 23 = 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 (24 = 16), a potem wyliczamy ich odpowiedniki
heksadecymalne. Jako przykład wez
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
4
Liczby: reprezentacja i prosta arytmetyka
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 0ogólności, jeżeli 0.d1, d2, ..., dn-1, dn są kolejnymi cyframi pewnego ułamka zapisanego przy
podstawie b, to zachodzi następujący związek:
(0.d1d2 ... di ... d-(n-1)dn)b = d1" b-1 + d2" b-2 + ... + di" b-i + ... + dn-1 " b-(n-1) + dn " b-n (5)
przy czym
0 < i < n (co oznacza, że liczba ma n+1 cyfr) (5a)
i
0 < di < b (co oznacza, że cyfry są liczbami nieujemnymi, mniejszymi od bazy) (5b)
Wez
my zapis dziesiętny (baza b = 10) i sprawdz
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
5
Liczby: reprezentacja i prosta arytmetyka
wrk = y * 2
di �! trunc ( wrk )
y �! wrk - di
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 (di �! trunc (y * 2)). Obliczenia kończą sie w momencie,
w którym część ułamkowa tego podwojenia jest zerem.
Wykorzystajmy algorytm (5) i przeprowadz
my konwersję ułamka dziesiętnego uzyskanego
jako rezultat w poprzednim przykładzie.
wrk di 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 di 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
6
Liczby: reprezentacja i prosta arytmetyka
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"1011 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"1011 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
7
Liczby: reprezentacja i prosta arytmetyka
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"1038 7
D 8 29"10-38 "! 1.7"1038 16
G 8 0.56"10-308 "! 0.9"10-308 15
H 16 0.84"10-4932 "! 0.59"104932 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.
8
Liczby: reprezentacja i prosta arytmetyka
a) b)
(*)2 0 1
(+)2 0 1
0 0 0
0 0 1
1 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 = 102, 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 102 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).
9
Liczby: reprezentacja i prosta arytmetyka
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.: 01 i 10) 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:
10
Liczby: reprezentacja i prosta arytmetyka
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 = 108, 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:
11
Liczby: reprezentacja i prosta arytmetyka
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 znalez
ć 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 28 liczbę 37 zapisaną na 8 bitach:
28 = (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 znalez
ć 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ą. Sprawdz
my:
12
Liczby: reprezentacja i prosta arytmetyka
-37 = (1101 1011)U2
0010 0100
+ 1
+37 = (0010 0101)2
Wykorzystajmy nabytą widzę i przeprowadz
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 -2n-1, a największa wartość to
(2n-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ę.
13
Liczby: reprezentacja i prosta arytmetyka
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 2n-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. A
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 =  25-1 =  16; maksymalna
liczba = 25-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.
14