Andrzej Szepietowski
25 marca 2004 roku
Arytmetyka
1.1
System dziesiętny
Najpowszechniej używanym sposobem przedstawiania liczb naturalnych jest system dziesiętny, gdzie na przykład zapis:
178
przedstawia liczbę składającą się z jednej setki, siedmiu dziesiątek i ośmiu jedności. Mo-
żemy to zapisać w postaci:
178 = 1 · 100 + 7 · 10 + 8 · 1,
albo inaczej:
178 = 1 · 102 + 7 · 101 + 8 · 100.
Tak więc w systemie dziesiętnym kolejne cyfry oznaczają współczynniki przy kolejnych potęgach liczby dziesięć, zaczynając od największej, a ko ńcząc na najmniejszej potędze.
Mówimy, że liczba dziesięć jest podstawą lub bazą systemu dziesiętnego. W systemie dziesiętnym używamy dziesięciu cyfr:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
a zapis:
drdr−1 . . . d1d0
oznacza liczbę:
dr · 10r + dr−1 · 10r−1 + . . . + d1 · 101 + d0 · 100,
(1.1)
którą możemy też zapisać w postaci:
r
X di ·10i,
(1.2)
i=0
3
4
Rozdział 1. Arytmetyka
gdzie di są cyframi należącymi do zbioru {0, . . . , 9}.
Liczby można też zapisywać w systemach z inną bazą. Jeżeli za bazę systemu wybie-rzemy liczbę b, to potrzebujemy b cyfr, a zapis:
drdr−1 . . . d1d0
oznacza w systemie z bazą b liczbę:
dr · br + dr−1 · br−1 + . . . + d1 · b1 + d0 · b0,
(1.3)
którą możemy też zapisać w postaci:
r
X di ·bi.
(1.4)
i=0
1.2
System dwójkowy
W informatyce bardzo ważnym systemem jest system dwójkowy (binarny), gdzie podstawą jest liczba 2 i gdzie mamy tylko dwie cyfry, 0 i 1 (cyfry w systemie dwójkowym nazywa się bitami). Zapis:
drdr−1 . . . d1d0
oznacza liczbę:
r
X di ·2i = dr ·2r +dr−1 ·2r−1 +...+d1 ·21 +d0 ·20.
i=0
Przykład 1.1 Zapis 110 oznacza w systemie dwójkowym liczbę 1 · 22 + 1 · 21 + 0 · 20 , czemu w systemie dziesiętnym odpowiada 4 + 2 = 6 .
Podobnie zapis 1101101 oznacza w systemie dziesiętnym liczbę 64+32+8+4+1 =
109 .
Poniżej w pierwszej tabeli przedstawiono jedenaście pierwszych potęg liczby 2 w postaci dwójkowej i dziesiętnej, a w drugiej siedemnaście kolejnych liczb w postaci dwójkowej i dziesiętnej.
potęga
dwójkowy
dziesiętny
0
1
1
1
10
2
2
100
4
3
1000
8
4
10000
16
5
100000
32
6
1000000
64
7
10000000
128
8
100000000
256
9
1000000000
512
10
10000000000
1024
1.3. Zwiększanie liczby o jeden
5
dwójkowy
dziesiętny
0
0
1
1
10
2
11
3
100
4
101
5
110
6
111
7
1000
8
1001
9
1010
10
1011
11
1100
12
1101
13
1110
14
1111
15
10000
16
1.3
Zwiększanie liczby o jeden
Algorytm zwiększania liczby o jeden. Aby zwiększyć o jeden liczbę zapisaną w systemie dwójkowym:
wskaż na ostatni bit,
powtarzaj, co następuje:
jeżeli wskazany bit jest zerem, to
zamień go na jedynkę i zako ńcz algorytm;
jeżeli jest on równy jeden, to
zamień go na zero i wskaż następny bit w lewo;
jeżeli nie ma następnego bitu w lewo,
to dostaw jedynkę na początku liczby i zako ńcz algorytm.
Mówiąc inaczej, szukamy pierwszego zera od prawej strony, zamieniamy go na jedynkę, a wszystkie jedynki stojące za nim zamieniamy na zera.
Przykład 1.2 Liczba o jeden większa od liczby 100100111 to 100101000 .
Jeżeli liczba nie zawiera zer, tylko same jedynki, to zamieniamy te jedynki na zera i stawiamy jedynkę na początku.
Przykład 1.3 Po liczbie 11111 jest liczba 100000 .
Zauważmy, że podobnie działa algorytm zwiększania o jeden liczb w systemie dziesiętnym (lub dowolnym innym systemie). Szukamy pierwszej od prawej cyfry różnej od dziewiątki (największej cyfry w systemie), zwiększamy tę cyfrę o jeden, a wszystkie stojące za nią dziewiątki zamieniamy na zera.
6
Rozdział 1. Arytmetyka
1.4
Porównywanie liczb
Algorytm porównywania liczb. Aby stwierdzić, która z dwóch liczb w postaci dwójkowej jest większa, postępuj w następujący sposób:
jeżeli liczby nie są tej samej długości, to większą jest dłuższym liczba
jeżeli liczby są równej długości, to
porównuj bit po bicie od lewej strony do prawej:
jeżeli bity są takie same, to
przejdź do następnego bitu w prawo,
jeżeli bity są różne, to
zakończ; większa jest liczba z większym bitem na tej pozycji,
jeżeli wszystkie bity są takie same, to porównywane liczby są równe.
Przykład 1.4 1011010 > 1010101 . Liczby te s ˛
a tej samej długości, maj ˛
a takie same trzy
pierwsze bity, a różni ˛
a się dopiero czwartym bitem — czwarty bit pierwszej liczby jest
większy od czwartego bitu drugiej liczby.
1.5
Operacje arytmetyczne w systemie dwójkowym
Operacje dodawania, mnożenia, odejmowania i dzielenia w systemie dwójkowym można wykonywać podobnie do tak zwanych szkolnych pisemnych działa ń arytmetycznych w systemie dziesiętnym. Działania w systemie dwójkowym są prostsze, ponieważ mamy tu tylko dwie cyfry, 0 i 1. Zacznijmy od tabliczki dodawania i mnożenia.
+
0
1
*
0
1
0
0
1
0
0
0
1
1
10
1
0
1
Algorytm dodawania.
Dane wejściowe: dwie liczby w postaci binarnej dr . . . d0, oraz er . . . e0. Zakładamy, że liczby są tej samej długości. Jeżeli nie są, to krótszą uzupełniamy na początku zerami.
Dane wyjściowe: bity sumy obu liczb sr+1sr . . . s0.
s0 := (d0 + e0) mod 2
c0 := d0 · e0;
dla kolejnych pozycji i od 1 do r oblicz
si := (di + ei + ci−1) mod 2,
ci := 1, jeżeli co najmniej dwa spośród bitów di, ei oraz ci−1 są jedynkami, sr+1 := cr.
Przykład 1.5 Dodawanie liczb 10101 i 111 wygl ˛
ada następuj ˛
aco:
1.5. Operacje arytmetyczne w systemie dwójkowym
7
1
0
1
0
1
+
1
1
1
1
1
1
0
0
Algorytm najpierw oblicza ostatni bit sumy s0, który jest resztą z dzielenia (d0 + e0) przez 2, oraz przeniesienie z ostatniego bitu c0. Następnie dla każdej pozycji i od 1 do r oblicza bit sumy si oraz przeniesienie do następnej pozycji. Na ko ńcu obliczany jest najbardziej znaczący bit sumy sr+1 = cr.
Aby odjąć od siebie dwie liczby w systemie dwójkowym, odejmujemy bit po bicie od prawej do lewej, a w przypadku gdy trzeba odjąć bit większy od mniejszego, „poży-czamy” dwójkę z następnej (w lewo) pozycji (szczegóły algorytmu pozostawiono jako ćwiczenie).
Przykład 1.6 Odejmowanie liczb 10101 i 111 wygl ˛
ada następuj ˛
aco:
1
0
1
0
1
−
1
1
1
1
1
1
0
Aby pomnożyć dwie liczby, mnożymy pierwszą liczbę przez poszczególne cyfry drugiej liczby, a wyniki podpisujemy pod spodem odpowiednio przesunięte względem siebie.
Każdy kolejny wynik jest przesunięty o jedną kolumnę w lewo. Następnie sumujemy te iloczyny.
Przykład 1.7 Oto przykład mnożenia liczb 10101 i 101 : 1
0
1
0
1
1
0
1
1
0
1
0
1
0
0
0
0
0
1
0
1
0
1
1
1
0
1
0
0
1
Zauważmy, że pomnożenie liczby w postaci dwójkowej przez dwa oznacza dopisanie jednego zera na ko ńcu liczby. Podobnie pomnożenie liczby przez i-tą potęgę dwójki oznacza dopisanie na ko ńcu i zer.
Przykład 1.8 1101101 pomnożone przez 1000 daje wynik 1101101000 .
Również dzielenie wykonuje się podobnie jak w systemie dziesiętnym. Na przykład: 1
0
1
0
1
1
1
0
1
0
0
1
:
1
0
1
1
0
1
1
1
0
1
0
1
1
0
1
1
0
1
0
0
0
Rozdział 1. Arytmetyka
Jeżeli liczba jest podzielna przez dwa, to ma w postaci binarnej zero na ko ńcu, a jeżeli dzieli się przez i-tą potęgę dwójki, to ma na ko ńcu i zer. Podzielenie liczby przez dwa oznacza skreślenie w jej postaci binarnej jednego zera z ko ńca.
Przykład 1.9 1010011000 podzielone przez dwa daje 101001100 .
1.6
Zamiana systemu
Zastanówmy się teraz, jak przechodzić od jednego sposobu przedstawiania liczby do dru-giego. Ponieważ będziemy używać różnych systemów zapisu liczb, więc zapis w systemie z bazą b oznaczymy przez:
(drdr−1 . . . d1d0)b.
Będziemy rezygnować z tego zapisu, jeżeli nie będzie wątpliwości, jakiego systemu używamy. Przedyskutujmy to na przykładach. Aby przedstawi ć liczbę
(110101)2
w postaci dziesiętnej, korzystamy ze wzoru (1.3):
(110101)2 = 1 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20,
i wykonujemy wszystkie rachunki w systemie dziesiętnym:
(110101)2 = 1 · 32 + 1 · 16 + 0 · 8 + 1 · 4 + 0 · 2 + 1 · 1 = 32 + 16 + 4 + 1 = (53)10.
Podobnie możemy postępować przy zamianie w odwrotną stronę, z systemu dziesiętnego na dwójkowy. Najpierw korzystamy ze wzoru (1.1):
(53)10 = 5 · 101 + 3 · 100,
następnie przedstawiamy cyfry i podstawę systemu 10 w postaci dwójkowej i wykonujemy wszystkie działania w systemie dwójkowym:
(53)10 = (101)2 · (1010)2 + (11)2 = (110010)2 + (11)2 = (110101)2.
Ten sposób zamiany liczb z postaci dziesiętnej na dwójkową jest analogiczny do sposobu, w jaki wyżej zamienialiśmy liczby z postaci dwójkowej na dziesiętną. Byłby to naturalny sposób dla kogoś, kto swobodnie liczy w systemie dwójkowym. Sposób ten ma tę wadę, że wolno działa. Zobaczymy na przykładach dwa szybsze algorytmy zamiany postaci liczby z dziesiętnej na dwójkową.
Weźmy liczbę 178. Pierwszy sposób polega na tym, że wyszukujemy największą po-tęgę liczby 2, która jeszcze jest mniejsza od naszej liczby (w przykładzie 128 = 27), następnie odejmujemy tę potęgę od naszej liczby i z różnicą postępujemy tak samo. Na końcu mamy liczbę w postaci sumy potęg dwójki. W naszym przykładzie wygląda to tak: 178 = 128 + 50 = 128 + 32 + 18 = 128 + 32 + 16 + 2.
1.6. Zamiana systemu
9
Teraz już łatwo zapisać naszą liczbę w postaci dwójkowej:
(178)10 = (10110010)2.
Drugi sposób polega na kolejnym dzieleniu liczby w sposób całkowity przez 2 i zapamiętywaniu reszt z dzielenia. Reszty te zapisane w odwrotnej kolejności tworzą zapis binarny liczby. Na przykład, weźmy znowu liczbę 178. W poniższej tabeli przedstawiono kolejne ilorazy i reszty.
liczba
iloraz
reszta
178
89
0
89
44
1
44
22
0
22
11
0
11
5
1
5
2
1
2
1
0
1
0
1
Reszty zapisane w odwrotnej kolejności:
10110010,
tworzą binarny zapis liczby (178)10. Poprawność działania tego algorytmu wynika z faktu, że jeżeli podzielimy liczbę
r
X
x =
di · 2i
i=0
przez 2, to reszta z dzielenia wyniesie d0, a iloraz całkowitoliczbowy wyniesie: r
X di ·2i−1,
i=1
następne dzielenie przez 2 da resztę d1 oraz iloraz:
r
X di ·2i−2,
i=2
i tak dalej.
Ostatni sposób można łatwo uogólnić na algorytm zamiany liczb z systemu dziesiętnego na system z inną bazą b. Należy tylko dzielić przez b. Aby przedstawić liczbę 60 w systemie trójkowym, dzielimy ją kolejno przez 3 i spisujemy reszty z dzielenia: liczba
iloraz
reszta
60
20
0
20
6
2
6
2
0
2
0
2
W wyniku otrzymamy:
(60)10 = (2020)3.
10
Rozdział 1. Arytmetyka
1.7
Długość liczby
Zastanówmy się ile cyfr zawiera zapis dziesiętny liczby naturalnej x. Cztery cyfry w systemie dziesiętnym posiadają liczby od 1000 = 103 do 9999 = 104 − 1, a k cyfr posiadają liczby od 10k−1 do 10k − 1. Tak więc liczba x ma k cyfr wtedy i tylko wtedy gdy k − 1 ≤ log x < k
x
10
, czyli gdy blog10 c = k − 1. Mamy więc
Lemat 1.10 Liczba naturalna x ma w systemie dziesiętnym blog x 10
c + 1 (w przybliżeniu
log
x
10
) cyfr.
Podobnie w systemie z podstawą b, liczba x ma k cyfr wtedy i tylko wtedy gdy k−1 ≤
log x < k, czyli:
b
Lemat 1.11 W systemie o podstawie b liczba naturalna x ma blog x b
c+1 (w przybliżeniu
log x ) cyfr.
b
Korzystając z tego faktu możemy ustalać przybliżoną liczbę cyfr potrzebną do zapisu liczb.
Wniosek 1.12 Liczba, posiadaj ˛
aca k cyfr w systemie dziesiętnym ma około k log 10
2
≈
k · 10 bitów w systemie dwójkowym, a liczba maj ˛
aca k bitów w postaci dwójkowej ma
3
około k · 3 cyfr w postaci dziesiętnej.
10
Dowód: Jeżeli liczba x ma w postaci dziesiętnej k cyfr, to k ≈ log x. W postaci dwój-10
kowej x ma około log x
x = log
10
10
2
bitów, a log2
10x · log2
≈ k · log2
≈ k · 10 ,
3
ponieważ log
2
.
10
≈ 0.301029996 ≈ 3
10
Podobnie, jeżeli liczba x ma w postaci dwójkowej k bitów, to w postaci dziesiętnej ma około log
x = log
x
10
102 · log2
≈ k · 3 .
10
1.8
Duże liczby
Aby się zorientować jak duże mogą być liczby przedstawione za pomocą systemu dziesiętnego lub dwójkowego przypatrzmy się poniższej tabeli:
Liczba sekund w roku
≈ 3 × 107
Wiek układu słonecznego w latach
≈ 1010
Wiek układu słonecznego w sekundach
≈ 1017
Liczba cykli w roku (100 MHz)
≈ 3 × 1015
Liczba ciągów 64 bitowych
264 ≈ 1.8 × 1019
Liczba ciągów 128 bitowych
2128 ≈ 3.4 × 1038
Liczba ciągów 256 bitowych
2256 ≈ 1.2 × 1077
Liczba atomów na Ziemi
≈ 1051
Liczba atomów w naszej galaktyce
≈ 1067
Dane do tabeli zaczerpnięto z książki A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography. oraz z książki B. Schneier, Applied Cryptography.
Tabela ta pozwala ocenić niektóre algorytmy.
1.9. Ułamki
11
Przykład 1.13 Rozważmy prosty algorytm sprawdzaj ˛
acy, czy liczba naturalna x jest pierw-
√
sza. Algorytm ten dzieli x przez kolejne liczby od 2 do
x . Jeżeli x ma 120 bitów, to
potrzeba 260 ≈ 1018 dzieleń. Jeżeli założymy, że komputer potrafi wykonać 100 milionów dzieleń w ci ˛
agu sekundy i 3×1015 w ci ˛
agu roku, to będzie liczył około 300 lat. W rozdziale
o teorii liczb będziemy mówić o szybszych algorytmach sprawdzaj ˛
acych pierwszość liczb
maj ˛
acych po kilkaset bitów.
Przykład 1.14 Przypuśćmy, że chcemy zaprojektować tablicę, która dla każdego ci ˛
agu
złożongo z ośmiu liter przechowuje jak ˛
aś informację (jeden bajt). Zakładaj ˛
ac, że mamy
26 liter, takich ci ˛
agów jest
268 = 108·log 26
10
= 108·1.41 > 1011,
zatem potrzebowalibyśmy więcej niż 100 gigabajtów pamięci.
1.9
Ułamki
Przypomnijmy najpierw krótko, jak przedstawia się ułamek w systemie dziesiętnym. Na przykład,
0.234
oznacza:
2 · 10−1 + 3 · 10−2 + 4 · 10−3.
Użyliśmy kropki do oddzielania części całkowitej od ułamkowej. Jest to często używany w informatyce sposób, stosowany między innymi w języku Pascal. Ogólniej, zapis: 0.d1d2 . . . dr
oznacza liczbę:
d1 · 10−1 + d2 · 10−2 + . . . + dr · 10−r,
którą możemy też zapisać w postaci:
r
X di ·10−i.
i=1
Podobnie możemy zapisywać ułamki w systemie dwójkowym. Jedyna różnica polega na tym, że w systemie binarnym podstawą potęg jest dwójka i że używamy tylko dwóch cyfr, 0 i 1. Tak więc w systemie dwójkowym zapis:
0.d1d2 . . . dr
oznacza liczbę:
d1 · 2−1 + d2 · 2−2 + . . . + dr · 2−r,
lub inaczej:
r
X di ·2−i.
i=1
12
Rozdział 1. Arytmetyka
Przykład 1.15
(0.1)2 = (0.5)10,
(0.11)2 = (0.75)10,
(0.101)2 = (0.625)10.
W poniższej tabeli przedstawiono kilka pierwszych ujemnych potęg liczby 2 w systemie dwójkowym i dziesiętnym.
2−1
(0.1)2
(0.5)10
2−2
(0.01)2
(0.25)10
2−3
(0.001)2
(0.125)10
2−4
(0.0001)2
(0.0625)10
2−5
(0.00001)2
(0.03125)10
2−6
(0.000001)2
(0.015625)10
1.10
System szesnastkowy
W informatyce używa się też systemu szesnastkowego, gdzie podstawą jest liczba 16. Do systemu szesnastkowego potrzebujemy szesnastu cyfr. Zwykle używa się następujących
„cyfr”:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
W poniższej tabeli zestawiono cyfry systemu szesnastkowego z odpowiadającymi im liczbami w systemie dwójkowym i dziesiętnym.
szesnastkowy
dwójkowy
dziesiętny
0
0000
0
1
0001
1
2
0010
2
3
0011
3
4
0100
4
5
0101
5
6
0110
6
7
0111
7
8
1000
8
9
1001
9
A
1010
10
B
1011
11
C
1100
12
D
1101
13
E
1110
14
F
1111
15
W języku Pascal liczby w systemie szesnastkowym poprzedza się znakiem dolara $, a w języku C znakami 0x.
1.11. Reprezentacja liczb w komputerze
13
Przykład 1.16 Zapis $A1 oznacza liczbę w systemie szesnastkowym, która w systemie dziesiętnym ma postać $A1 = 10 · 16 + 1 = (161)10
Dzięki temu, że 16 jest potęgą dwójki, prosta jest zamiana postaci liczby z systemu dwójkowego na szesnastkowy, i na odwrót. Przy zamianie z systemu szesnastkowego na dwójkowy wystarczy zamieniać kolejne cyfry przedstawienia na grupy odpowiednich czterech bitów według powyższej tabeli.
Przykład 1.17 Liczba, która w systemie szesnastkowym wygl ˛
ada tak $A91 w systemie
dwójkowym ma postać 1010|1001|0001 .
Przy zamianie z postaci dwójkowej na postać szesnastkową postępujemy odwrotnie. Za-stępujemy grupy po cztery bity pojedynczymi cyframi.
Przykład 1.18 (1110|0011|1011|0000)2 = $E3B0 .
Jeżeli liczba cyfr w postaci dwójkowej nie dzieli się przez 4, to uzupełniamy ją zerami na początku.
Przykład 1.19 (110|1111|0110|0010)2 = (0110|1111|0110|0010)2 = $6F 62 .
W ten sposób możemy używać zapisu szesnastkowego do zwięzłego przedstawiania dłu-gich ciągów bitów.
1.11
Reprezentacja liczb w komputerze
W wielu językach każda zmienna ma swój typ, który jest deklarowany na początku pro-gramu. Sposób przechowywania wartości zmiennej zależy od jej typu.
1.11.1
Integer
Zmienne typu integer przechowywane są zwykle w dwóch bajtach. Jeden bajt (ang. by-te) zawiera osiem bitów, tak więc wartość zmiennej typu integer przechowywana jest w szesnastu bitach. Pierwszy bit oznacza znak. Jeżeli jest on zerem, to liczba jest dodatnia, jeżeli jedynką, to ujemna.
Jeżeli liczba jest dodatnia, to pozostałe piętnaście bitów stanowi binarny zapis tej liczby. Na przykład liczba 15 jest przechowywana jako:
0000|0000|0000|1111.
Największą liczbę dodatnią, jaką można przechować w zmiennej typu integer, jest: 0111|1111|1111|1111,
czyli zero i piętnaście jedynek. Jest to:
215 − 1 = (32767)10.
Rozdział 1. Arytmetyka
Liczby ujemne są przechowywane w tak zwanym systemie uzupełnieniowym. Liczba ujemna x o wartości bezwzględnej |x| jest przedstawiana jako liczba:
216 − |x|
w postaci binarnej. Na przykład liczba −1 jest przedstawiona jako:
1111|1111|1111|1111,
czyli szesnaście jedynek. A liczba −3 jako:
1111|1111|1111|1101.
Najmniejsza liczba ujemna, którą można zmieścić do zmiennej typu integer, to: 1000|0000|0000|0000,
czyli jedynka i piętnaście zer, która koduje liczbę:
−215 = (−32768)10.
Często nie ma żadnego zabezpieczenia przed przekroczeniem maksymalnego lub mini-malnego zakresu liczb typu integer. Jeżeli, na przykład, do liczby 32767, która jest przechowywana jako:
0111|1111|1111|1111,
dodamy jedynkę, to otrzymamy:
1000|0000|0000|0000,
która koduje liczbę −32768, i komputer nie zakomunikuje tego przekroczenia.
1.11.2
Real
Liczby typu real są zapisywane w dwóch notacjach:
• stałopozycyjnej,
• zmiennopozycyjnej.
Liczby w notacji stałopozycyjnej to, na przykład:
0.10,
11.023,
12.0,
czyli notacja dziesiętna. Zwróćmy uwagę, że kropka oddziela część całkowitą liczby od części ułamkowej.
W notacji zmiennopozycyjnej liczba przedstawiona jest w postaci:
mEc,
gdzie m jest mantys ˛
a, liczbą w postaci dziesiętnej z przedziału 1 ≤ m < 10 lub −10 < m ≤ −1, a c, zwana cech ˛
a, jest liczbą całkowitą. Zapis mEc oznacza liczbę:
m · 10c.
W poniższej tabeli mamy kilka liczb w postaci stało- i zmiennopozycyjnej.
1.12. Wyrażenia arytmetyczne w języku Pascal
15
4837.92
4.83792E3
0.034
3.4E − 2
−12.0
−1.2E1
Sposób przechowywania wartości zmiennych typu real jest skomplikowany i nie będzie przedstawiony szczegółowo.
1.11.3
Inne typy całkowite
W języku Pascal, oprócz integer, można używać innych typów całkowitych; są to:
• shortint, zawiera liczby całkowite z przedziału od −128 do 127,
• byte, zawiera liczby całkowite z przedziału od 0 do 255,
• word, zawiera liczby całkowite z przedziału od 0 do 65535,
• longint, zawiera liczby całkowite z przedziału od −2147483648 do 2147483647.
Elementy typu byte i shortint przechowywane są w jednym bajcie (osiem bitów) pa-mięci, typu word — w dwóch bajtach, a typu longint — w czterech bajtach pamięci.
Liczby typu shortint i longint mogą być dodatnie lub ujemne i są zapamiętywane w postaci uzupełnieniowej z pierwszym bitem oznaczającym znak (podobnie jak liczby typu integer). Elementy typu byte i word mogą być tylko dodatnie i są przechowywane w postaci dwójkowej.
1.12
Wyrażenia arytmetyczne w języku Pascal
W języku Pascal wyrażeniami arytmetycznymi są stałe liczbowe, na przykład: 234,
−123,
0.123,
−23.45,
3.21E − 5,
oraz zmienne typów liczbowych (np. integer lub real). Wyrażenia można także budowa ć za pomocą operatorów arytmetycznych i nawiasów. Jeżeli U oraz W są dwoma wyrażeniami arytmetycznymi, to wyrażeniami arytmetycznymi są także:
U+W, U-W, U*W, U/W, (U), U div V, U mod V.
Gwiazdka ∗ reprezentuje tutaj znak mnożenia, a operacje div oraz mod to iloraz i reszta z dzielenia całkowitoliczbowego (są one opisane dokładnie w rozdziale o teorii liczb).
Na przykład, wyrażeniami arytmetycznymi są:
-(2-3)/2+7*4, (2-3)/(3*2), 7 div 2, 7 mod 2.
Jeżeli x oraz y są zmiennymi liczbowymi, to wyrażeniami arytmetycznymi są także: 2*x, x*x-2/y.
Dla danego wyrażenia możemy obliczyć jego wartość. Robi się to według zwykłych reguł
znanych ze szkoły. Najpierw oblicza się wyrażenia w nawiasach, potem mnożenie i dzielenie (od lewej do prawej), a na ko ńcu dodawanie i odejmowanie (od lewej do prawej).
Rozdział 1. Arytmetyka
1.13
Poszukiwania binarne (binary search)
Znana jest gra w dwadzieścia pytań. W tej grze za pomocą dwudziestu pyta ń, na które odpowiedzią może być „tak” lub „nie”, należy odgadnąć pomyślaną przez przeciwnika rzecz. Zobaczymy, jak można wykorzystać binarny system zapisu liczb do opracowania strategii wygrywającej w tej grze.
Uprośćmy nieco tę grę. Załóżmy, że możemy zadać tylko trzy pytania i że odgadujemy liczbę naturalną x ze zbioru:
A = {0, 1, 2, 3, 4, 5, 6, 7}.
Aby odgadnąć liczbę należy postępować w następujący sposób: Najpierw dzielimy zbiór na połowy: na liczby mniejsze od 4:
{0, 1, 2, 3}
i na liczby większe lub równe 4:
{4, 5, 6, 7}
i pytamy, do której połowy należy odgadywana liczba (dokładniej pytamy, czy liczba należy do górnej połowy). Po uzyskaniu odpowiedzi mamy dwa razy węższy przedział
poszukiwa ń i postępujemy z nim podobnie jak w pierwszej turze, dzielimy go na połowy i pytamy, w której połowie jest szukana liczba. Po drugiej odpowiedzi przedział poszukiwań jest już cztery razy krótszy i zawiera dwie liczby. W trzecim pytaniu, znowu dzielimy przedział na polowy i pytamy, w której połowie znajduje się szukana liczba. Po trzeciej odpowiedzi przedział poszukiwa ń jest już osiem razy krótszy od wyjściowego i zawiera jedną liczbę, która jest tą szukaną.
Prześledźmy ten algorytm w przypadku, gdy szukaną liczbą x jest 5. Po odpowiedzi na pierwsze pytanie wiemy, że x jest w zbiorze {4, 5, 6, 7}. W drugiej rundzie dzielimy ten zbiór na połowy: {4, 5} oraz {6, 7} i pytamy, czy x jest w górnej połowie. Po negatywnej odpowiedzi wiemy, ze x jest w {4, 5}. W trzeciej rundzie pytamy, czy x = 5.
Strategię gry w trzy pytania można przedstawić za pomocą ukorzenionego drzewa, patrz rysunek 1.1. Grę rozpoczynamy w korzeniu (wierzchołku z etykietą λ). Z tym wierzchołkiem związany jest cały zbiór {0, 1, 2, 3, 4, 5, 6, 7}. Z synami korzenia związane są połówki tego zbioru, z wierzchołkiem 1 związany jest zbiór {4, 5, 6, 7}, a z wierzchoł-
kiem 0 zbiór {0, 1, 2, 3}. Jeżeli po odpowiedzi na pierwsze pytanie dowiemy się, że szukana liczba jest w górnej połowie, to przechodzimy do wierzchołka 1, w przeciwnym przypadku przechodzimy do 0. Ogólnie, jeżeli z wierzchołkiem z etykietą ω związany jest zbiór Aω i ten zbiór ma więcej niż jeden element, to prawy syn tego wierzchołka ma etykietę ω1 i jest z nim związana górna połowa zbioru Aω, a lewy syn ma etykietę ω0 i jest z nim związana dolna połowa zbioru Aω. Jeżeli w toku gry trafimy do wierzchołka z etykietą ω, to pytamy, czy szukany element znajduje się w górnej, czy w dolnej połowie zbioru Aω i po uzyskaniu odpowiedzi przechodzimy do odpowiedniego syna. Wierzcho-
łek jest liściem, jeżeli związany z nim zbiór ma tylko jeden element.
Jeżeli szukanym elementem jest 5, to z wierzchołka λ przejdziemy do wierzchołka 1, potem do 10, a na koniec trafimy do wierzchołka 101, który jest związany ze zbiorem jed-noelementowym {5}. Nie jest przypadkiem, że etykieta wierzchołka odpowiada postaci
1.13. Poszukiwania binarne (binary search)
17
Rysunek 1.1:
λ
0
1
00
01
10
11
000
001
010
011
100
101
110
111
dwójkowej liczby, którą zawiera. Tak dobraliśmy bowiem zbiór wyjściowy A. Możemy powiedzieć, że zawiera on wszytkie liczby trzy bitowe
A = {000, 001, 010, 011, 100, 101, 110, 111}.
Liczby ze zbioru A1 = {100, 101, 110, 111} związanego z wierzchołkiem 1 mają pierwszy bit równy 1, a liczby ze zbioru A0 = {000, 001, 010, 011} związanego z wierzchoł-
kiem 0 mają pierwszy bit równy 0, i ogólnie liczby ze zbioru Aω związanego z wierzchoł-
kiem ω mają swoje pierwsze bity równe ω. Na przykład z wierzchołkiem 10 związany jest zbiór A10 = {100, 101}.
Zauważmy także, że kolejne pytania, są pytaniami o kolejne bity szukanej liczby.
W pierwszym pytaniu pytamy o pierwszy, w drugim o drugi, a w trzecim o trzeci bit szukanej liczby. Oczywiście taka zgodność pomiędzy bitami szukanej liczby i etykietami wierzchołków drzewa nie wystąpi przy innym ponumerowaniu elementów wyjściowego zbioru.
Jak zobaczyliśmy trzeba trzy razy kolejno dzielić zbiór na połowy, aby z początkowego zbioru 8 elemntowego dojść na końcu do zbiorów jednoelementowych. A ile trzeba podziałów, jeżeli na początku mamy n = 2k elementów? Po pierwszym podziale nasz zbiór będzie miał 2k−1 elementów, po drugim 2k−2, a po i-tym 2k−i. Jak widać, potrzeba k = log n
2
kolejnych podziałów, aby dojść do zbioru jednoelementowego. Tak więc jeżeli mamy do dyspozycji 20 pyta ń, to możemy odnaleźć jedną spośród 220 liczb całkowitych z przedziału od 0 do 220 − 1 = 1 048 575.
18
Rozdział 1. Arytmetyka
1.13.1
Poszukiwanie pierwiastka
Metodę poszukiwa ń binarnych można zastosować do stwierdzenia, czy jakaś liczba naturalna n jest kwadratem (lub jakąś inną ustaloną potęgą) innej liczby naturalnej. Inaczej, czy istnieje liczba naturalna k taka, że k2 = n, lub ogólniej, czy istnieje liczba naturalna k taka, że kα = n.
Poniżej przedstawiamy taki algorytm. Algorytm ten używa dwoch dodatkowych zmiennych kd i kg, wartości tych zmiennych przybliżają pierwiastek stopnia α z n od dołu i od góry. W trakcie wykonywania algorytmy przybliżeniaa te są coraz lepsze
Algorytm sprawdzający, czy dana liczba naturalna n jest potęgą o wykładniku α jakiejś liczby naturalnej.
Dane wejściowe: liczba naturalna n.
Dane wyjściowe: pierwiastek stopnia α z n, (liczba naturalna m, taka że mα = n) lub informacja, że n nie ma naturalnego pierwiastka stopnia α.
kd := 1; kg := n;
Powtarzaj aż do skutku:
jeżeli kg − kd ≤ 1, to
koniec, n nie ma pierwiastka.
w przeciwnym przypadku
j := b kd+kg c
2
jeżeli jα = n , to koniec, n jest potęgą j.
jeżeli jα > n , to kg := j
jeżeli jα < n , to kd := j.
1.14
Zadania
1. Zwiększ o jeden liczby: a)
(11010011)2, b) (111111)2, c) (2012)3, d) (2013)4.
2. Porównaj pary liczb: a)
(110011)2, (110100)2, b) (11010)2, (1110)2, c) (12121)3,
(12201)3, d) (33132)4, (33201)4.
3. Dodaj (odejmij, pomnóż) następujące pary liczb: a) (110011)2, (110100)2; b)
(11010)2, (1110)2; c) (11101)2, (1111)2.
4. Dodaj w postaci trójkowej liczby (2101)3 oraz (1212)3.
5. Napisz dokładny algorytm odejmowania dwóch liczb w postaci dwójkowej.
6. Liczby (81)10, (126)10, (200)10, (257)10, (258)10, (1025)10, (1023)10 przedstaw w postaci dwójkowej i ósemkowej.
7. Jak liczby 4, 20, −4, −20 będą reprezentowane w komputerze jako stałe typu integer (byte, word)?
8. Liczby $B1, $FF przedstaw w postaci dziesiętnej, dwójkowej i ósemkowej.
1.15. Problemy
19
9. Liczby (80)10, (120)10 przedstaw w postaci trójkowej.
10. Liczby (10001101)2, (100101)2, przedstaw w postaci: dziesiętnej, szesnastkowej i ósemkowej.
11. Liczby (1023)8, (713)8 przedstaw w postaci dwójkowej i dziesiętnej.
12. Ułamki (0.5625)10, (0.140625)10 przedstaw w postaci dwójkowej.
13. Ułamki (0.1101)2, (0.01101)2, (0.0011)2 przedstaw w postaci dziesiętnej.
14. Opisz algorytm zamiany ułamka z postaci dziesiętnej na posta ć dwójkową.
15. Ile maksymalnie pyta ń z odpowiedziami TAK/NIE trzeba zadać, aby odgadnąć liczbę: a) z przedziału od 0 do 100 000 b) z przedziału od 0 do 1 000 000?
16. Zastosuj algorytm wyznaczania pierwiastków do znalezienia następujących pier-
√
√
√
√
wiastków: 2 256, 2 1000, 3 512, 4 256.
17. Sprawdź, czy liczby 111, 1111 są potęgami liczb całkowitych.
1.15
Problemy
1.15.1
Uzupełnieniowy zapis liczb ujemnych
Aby całkowitą liczbę ujemną x z przedziału od −32768 do −1 przedstawić w postaci uzupełnieniowej na dwóch bajtach:
• zapisz wartość bezwzględną |x| w postaci dwójkowej na szesnastu bitach.Jeżeli zapis jest krótszy niż szesnaście bitów, uzupełnij go na początku zerami.
• Zamień wszystkie szesnaście bitów: 0 na 1, a 1 na 0,
• Dodaj 1.
Wypróbuj ten sposób na kilku liczbach. Udowodnij, że działa on prawidłowo.
1.15.2
Liczby w postaci ósemkowei i szesnastkowej w języku C
Jak w języku C można zapisać liczby (stałe) w systemie ósemkowym lub szesnastkowym.
Jak w C zadać format, aby liczba całkowita została wydrukowana w systemie ósemkowym lub szesnastkowym.
1.15.3
Sumy potęg dwójki
Udowodnij, że jeżeli liczby a1, ... ,ak są różnymi potęgami dwójki, to dla każdego pod-zbioru I ⊂ {1, 2, . . . , k} suma
X ai
i∈I
jest inna. Pokaż, że tak nie musi być w przypadku dowolnego ciągu różnych liczb.
20
Rozdział 1. Arytmetyka
1.15.4
Waga
Wyobraźmy sobie wagę szalkową. Na jednej szalce, lewej, kładziemy jakiś przedmiot do zważenia, a następnie na obu szalkach kładziemy odważniki. Jeżeli waga jest w równowa-dze, to ważony przedmiot ma wagę równą sumie (nominałów) odważników położonych na prawej szalce minus suma odważników położonych na lewej szalce, obok ważonego przedmiotu. Na przykład, jeżeli na prawej szalce leżą odważniki 2 i 20 gramowe, a na lewej odważniki 4 i 5 gramowe, to przedmiot waży 13 = (20 + 2) − (5 + 4) gramów.
Interesujące nas pytanie brzmi: jakie powinny być nominały poszczególnych odważ-
ników, aby można było zważyć każdy ciężar o wadze od 1 do N , przy jak najmniejszej liczbie odważników. Zakładamy, że ważymy tylko przedmioty o wagach będących dodat-nimi liczbami naturalnymi.
Pokaż, że
(1) Za pomocą k odważników można zważyc co najwyżej 3k−1 różnych ciężarów.
2
(2) Jeżeli nominały odważników są kolejnymi potęgami trójki, to znaczy ci = 3i dla 0 ≤ i ≤ k − 1, to za ich pomocą można zważyć każdy ciężar o nominale od 1 do 3k −1 .
2
(3) Jak należy ułożyć na szalkach odważniki o nominałach 1, 3, 9, 27, aby odważyc ciężar: a) 35, b) 29?
(4) Ile potrzeba odważników, aby zważyć każdy ciężar a) od 1 do 100, b) od 1 do 1000?
(5) Jak należy ułożyć na szalkach odważniki o nominałach będących potęgami trójki aby odważyc ciężar: a) 50, b) 200, c) 500?
Wskazówki:
(1) Ponieważ każdy odważnik może się znajdować na prawej lub lewej szalce, lub na stole, to mamy 3k różnych położe ń odważników. Wśród tych położe ń jest takie, gdzie wszystkie odważniki leżą na stole (wtedy ważymy zerowy ciężar). Ponadto jeżeli od-ważniki leżą na szalkach i odważają ciężar W , to zamieniwszy położenia odważników na szalkach (odważniki z lewej przekładamy na prawą szalkę, i na odwrót), będziemy odważać ciężar −W .
(2) Rozłożenie odważników przy ważeniu ciężaru W odpowiada przedstawieniu W w postaci
k−1
X
W =
di3i,
(1.5)
i=0
gdzie di ∈ {−1, 0, 1}. Aby przedstawić ciężar W w postaci (1.5), najpierw przedstawiamy liczbę W + 3k−1 w systemie trójkowym: W + 3k−1 = (e
2
2
k−1 . . . e1e0)3, a następnie
od każdej cyfry odejmujemy jedynkę: di = ei − 1.