arytmetyka.pdf

Matematyka dyskretna

Arytmetyka

Andrzej Szepietowski

1 System dziesietny

Najpowszechniej uzywanym sposobem przedstawiania liczb naturalnych jest system dziesietny,

gdzie na przyklad zapis:

178

przedstawia liczbe skladajaca sie z jednej setki, siedmiu dziesiatek i osmiu jednosci. Mozemy to

zapisac w postaci:

178 = 1100 + 710 + 81;

178 = 110 2 + 710 1 + 810 0 :

Tak wiec w systemie dziesietnym kolejne cyfry oznaczaja wspolczynniki przy kolejnych potegach

liczby dziesiec, zaczynajac od najwiekszej, a konczac na najmniejszej potedze. Mowimy, ze liczba

dziesiec jest podstawa lub baza systemu dziesietnego. W systemie dziesietnym uzywamy dziesieciu

cyfr:

0; 1; 2; 3; 4; 5; 6; 7; 8; 9;

a zapis:

d r d r 1 : : : d 1 d 0

oznacza liczbe:

d r 10 r + d r 1 10 r 1 + : : : + d 1 10 1 + d 0 10 0 ;

(1)

ktora mozemy tez zapisac w postaci:

r X

d i 10 i ;

(2)

i=0

gdzie d i sa cyframi nalezacymi do zbioruf0; : : : ; 9g.

Liczby mozna tez zapisywac w systemach z inna baza. Jezeli za baze systemu wybierzemy liczbe

b, to potrzebujemy b cyfr, a zapis:

d r d r 1 : : : d 1 d 0

oznacza w systemie z baza b liczbe:

d r b r + d r 1 b r 1 + : : : + d 1 b 1 + d 0 b 0 ;

(3)

ktora mozemy tez zapisac w postaci:

r X

d i b i :

(4)

i=0

albo inaczej:

2 System dwojkowy

W informatyce bardzo waznym systemem jest system dwojkowy (binarny), gdzie podstawa jest

liczba 2 i gdzie mamy tylko dwie cyfry, 0 i 1 (cyfry w systemie dwojkowym nazywa sie bitami).

Zapis:

d r d r 1 : : : d 1 d 0

oznacza liczbe:

d r 2 r + d r 1 2 r 1 + : : : + d 1 2 1 + d 0 2 0

lub:

r X

d i 2 i :

i=0

Na przyklad, zapis 110 oznacza w systemie dwojkowym liczbe:

12 2 + 12 1 + 02 0 ;

czemu w systemie dziesietnym odpowiada:

4 + 2 = 6:

Podobnie zapis:

1101101

oznacza w systemie dziesietnym liczbe:

64 + 32 + 8 + 4 + 1 = 109:

W ponizszej tabeli przedstawiono kilkanascie kolejnych liczb w postaci dwojkowej i dziesietnej, a w

nastepnej | kilkanascie pierwszych poteg liczby 2 w postaci dwojkowej i dziesietnej.

dwojkowy dziesietny

100

101

110

111

1000

1001

1010

1011

1100

1101

1110

1111

10000

potega

dwojkowy dziesietny

100

1000

10000

100000

1000000

10000000

128

100000000

256

9 1000000000

512

10 10000000000

1024

3 Zwiekszanie liczby o jeden

Algorytm zwiekszania liczby o jeden. Aby zwiekszyc o jeden liczbe zapisana w systemie

dwojkowym:

wskazujemy na ostatni bit,

powtarzamy, co nastepuje:

jezeli wskazany bit jest zerem, to zamieniamy go na jedynke i konczymy algorytm,

jezeli jest on rowny jeden, to zamieniamy go na zero i wskazujemy nastepny bit w lewo;

jezeli nie ma nastepnego bitu w lewo, to stawiamy jedynke na poczatku liczby i konczymy

algorytm.

Mowiac inaczej, szukamy pierwszego zera od prawej strony, zamieniamy go na jedynke, a wszystkie

jedynki stojace za nim zamieniamy na zera. Na przyklad, liczba o jeden wieksza od liczby

100100111

100101000:

Jezeli liczba nie zawiera zer, tylko same jedynki, to zamieniamy te jedynki na zera i stawiamy

jedynke na poczatku. Na przyklad, po liczbie

11111

jest liczba

100000:

Zauwazmy, ze podobnie dziala algorytm zwiekszania o jeden liczb w systemie dziesietnym (lub

dowolnym innym systemie). Szukamy pierwszej od prawej cyfry roznej od dziewiatki (najwiekszej

cyfry w systemie), zwiekszamy te cyfre o jeden, a wszystkie stojace za nia dziewiatki zamieniamy

na zera.

4 Porownywanie liczb

Algorytm porownywania liczb. Aby stwierdzic, ktora z dwoch liczb jest wieksza, postepujemy

w nastepujacy sposob:

jezeli zapisy liczb nie sa tej samej dlugosci, to wieksza jest liczba z dluzszym zapisem (zakladamy

tu, ze zapis liczby roznej od zera nie ma zer na poczatku),

jezeli zapisy liczb sa rownej dlugosci, to porownujemy bit po bicie od lewej strony do prawej:

jezeli bity sa takie same, to przechodzimy do nastepnego bitu w prawo,

jezeli bity sa rozne, to konczymy i stwierdzamy, ze wieksza jest ta liczba, ktora ma

wiekszy bit na tej pozycji,

jezeli wszystkie bity sa takie same, to porownywane liczby sa rowne.

Na przyklad:

1011010 > 1010101:

Powyzsze liczby sa tej samej dlugosci i maja takie same trzy pierwsze bity, a roznia sie dopiero

czwartym bitem | czwarty bit pierwszej liczby (1) jest wiekszy od czwartego bitu drugiej liczby

(0).

5 Operacje arytmetyczne w systemie dwojkowym

Operacje dodawania, mnozenia, odejmowania i dzielenia w systemie dwojkowym mozna wykonywac

podobnie do tak zwanych szkolnych pisemnych dzialan arytmetycznych w systemie dziesietnym.

Dzialania w systemie dwojkowym sa prostsze, poniewaz mamy tu tylko dwie cyfry, 0 i 1, i prostsze

sa operacje na pojedynczych cyfrach.

Zacznijmy od tabliczki dodawania i mnozenia. Wygladaja one tak:

+ 0 1

0 0 1

1 1 10

* 0 1

0 0 0

1 0 1

Przypuscmy, ze chcemy dodac dwie liczby w postaci dwojkowej. Zakladamy tu, ze obie liczby sa

tej samej dlugosci. Jezeli nie sa, to krotsza z nich uzupelniamy na poczatku zerami.

Algorytm dodawania. Aby dodac dwie liczby w postaci binarnej:

d r d r 1 : : : d 0 ;

e r e r 1 : : : e 0 ;

dla kolejnych pozycji i od 0 do r obliczamy bit sumy s i

oraz c i

| tak zwany bit przeniesienia do

nastepnej pozycji:

najpierw obliczamy s 0 oraz c 0 :

s 0 = d 0 + e 0 (mod 2)

(czyli s 0 jest reszta z dzielenia d 0 + e 0 przez 2),

c 0 = d 0 e 0 ;

nastepnie po kolei, dla kazdego i od 1 do r, obliczamy i-ty bit sumy wedlug wzoru:

s i = d i + e i + c i 1 (mod 2);

a bit c i

jest jedynka, jezeli co najmniej dwa sposrod bitow d i , e i

oraz c i 1

sa jedynkami,

na koncu obliczamy najbardziej znaczacy bit sumy:

s r+1 = c r :

Wynikiem dodawania jest liczba

s r+1 s r : : : s 0

(moze sie zdarzyc, ze s r+1 = 0).

Na przyklad, dodawanie liczb 10101 i 111 wyglada nastepujaco:

1 0 1 0 1

1 1 1

1 1 1 0 0

Aby odjac od siebie dwie liczby w systemie dwojkowym, odejmujemy bit po bicie od prawej do lewej,

a w przypadku gdy trzeba odjac bit wiekszy od mniejszego, ,,pozyczamy" dwojke z nastepnej (w

lewo) pozycji (szczegoly algorytmu pozostawiono jako cwiczenie). Na przyklad, odejmowanie liczb

10101 i 111 wyglada nastepujaco:

1 0 1 0 1

1 1 1

1 1 1 0

Aby pomnozyc dwie liczby, mnozymy pierwsza liczbe przez poszczegolne cyfry drugiej liczby, a

wyniki podpisujemy pod spodem odpowiednio przesuniete wzgledem siebie. Kazdy kolejny wynik

jest przesuniety o jedna kolumne w lewo. Nastepnie sumujemy te iloczyny. Oto przyklad mnozenia

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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: