Arytmetyka komputerowa

Systemy liczbowe

System binarny

Wszyscy jesteśmy dobrze obeznani z używanym w zapisie liczb systemem dziesiętnym. W komputerach używamy jednak najczęściej systemu dwójkowego. Zasada zapisu jest taka sama jak w systemie dziesiętnym, używamy jednak tylko dwóch cyfr (0 i 1) i kolejne cyfry oznaczają konieczność dodania kolejnych potęg dwójki. Dla przykładu:

\[ (110101101)_2 = 1 \cdot 2^0 + 0 \cdot 2^1 + 1 \cdot 2^2 + 1 \cdot 2^3 + 0 \cdot 2^4 + 1 \cdot 2^5 + 0 \cdot 2^6 + 1 \cdot 2^7 + 1 \cdot 2^8 = (429)_{10} \]

Aby zamienić liczbę z systemu dziesiętnego na dwójkowy, dzielimy ją kolejno przez 2. Pojawiające się reszty z dzielenia (0 lub 1) to kolejne cyfry w zapisie dwójkowym. Zapis dwójkowy liczby odczytujemy od końca:

\[ \begin{array}{r|l} 7521 & 1 \\ 3760 & 0 \\ 1880 & 0 \\ 940 & 0 \\ 470 & 0 \\ 235 & 1 \\ 117 & 1 \\ 58 & 0 \\ 29 & 1 \\ 14 & 0 \\ 7 & 1 \\ 3 & 1 \\ 1 & 1 \\ \end{array} \]

Zatem \((7521)_{10} = (1110101100001)_2\) .

W systemie binarnym możemy też zapisywać ułamki. Kolejne cyfry po przecinku oznaczają kolejne potęgi liczby 2. Na przykład:

\[ (0,110101)_2 = 1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 0 \cdot 2^{-3} + 1 \cdot 2^{-4} + 0 \cdot 2^{-5} + 1 \cdot 2^{-6} = \frac{53}{64} = (0,828125)_{10} \]

Aby zamienić liczbę mniejszą od 1 na ułamek binarny, mnożymy ją kolejno przez 2. Za każdym razem, gdy wynik jest większy od 1, odpowiednia cyfra to 1, w przeciwnym przypadku 0. Za każdym razem mnożymy tylko część ułamkową. Na przykład:

\[ \begin{array}{r|l} 0{,}1 & 0,\\ 0{,}2 & 0 \\ 0{,}4 & 0 \\ 0{,}8 & 0 \\ 1{,}6 & 1 \\ 1{,}2 & 1 \\ 0{,}4 & 0 \\ 0{,}8 & 0 \\ 1{,}6 & 1 \\ 1{,}2 & 1 \\ \dots & \\ \end{array} \]

Widzimy, że \((0{,}1)_{10} = (0{,}0\underline{0011})_2\) .

Każdy skończony ułamek binarny jest liczbą o skończonym rozwinięciu dziesiętnym. Niestety, skończone ułamki dziesiętne często nie mają skończonych rozwinięć dwójkowych (tak jak powyżej). Jest to problematyczne w zastosowaniach finansowych, gdzie często oblczenia muszą być prowadzone w systemie dziesiętnym.

System ósemkowy i szesnastkowy

Co prawda współczesne komputery używają systemu binarnego, w komunikacji z komputerami jendak czasem łatwiej stosować inne systemy liczbowe łatwo tłumaczące sie na system binarny. Jeżeli pogrupujemy cyfry binarne po trzy (od przecinka w obie strony, w razie potrzeby uzupełniając zerami) i każdej grupie przypiszemy jej wartość w systemi binarnym, otrzymamy rozwinięcie ósemkowe. Na przykład:

\[ (10101111{,}1)_2 = (010 101 111{,}100)_2 = (257{,}4)_8 \]

Jeżeli postąpimy analogicznie, lecz pogrupujemy cyfry po cztery, dostaniemy rozwinięcie szesnastkowe. Przy próbie zapisu będziemy potrzebowali cyfr większych od 9 (dla cyfr o wartościach 10, 11, 12, 13, 14 i 15), standardowo używamy w tym celu liter A, B, C, D, E, F. Na przykład:

\[ (10101111{,}1)_2 = (1010 1111{,}1000)_2 = (AF{,}8)_{16} \]

W języku C/C++ liczby w systemie ósemkowym zapisujemy pisząc 0 na początku. Liczby w systemie szesnastkowym, pisząc na początku 0x. Jest to bardzo wygodne, ale należy uważać, zwłaszcza z systemem ósemkowym. Na przykład w języku C/C++ \(77 \neq 077\) (pierwszy zapis jest w systemie dziesiętnym, drugi w ósemkowym).

Inne systemy liczbowe

Oczywiście nic nie stoi na przeszkodzie byśmy używali innych systemów liczbowych, choć w praktyce pojawiają się one rzadko (system o podstawie 64 jest używany często przy przesyłaniu wiadomości email). Konwersja z systemu dziesiętnego na każdy inny system działa na tej samej zasadzie co konwersja na system binarny – kolejno mnożymy bądź dzielimy przez podstawę systemu, pojawiające się reszty bądź części całkowite ułamków to kolejne cyfry. Dla przykładu poniżej konwersja liczby całkowitej na system o podstawie 6:

\[ \begin{array}{r|l} 7521 & 3 \\ 1253 & 5 \\ 208 & 4 \\ 34 & 4 \\ 5 & 5 \\ \end{array} \]

Stąd \((7521)_{10} = (54453)_6\) .

Poniżej konwersja ułamka na system o podstawie 3:

\[ \begin{array}{r|l} 0{,}1 & 0,\\ 0{,}3 & 0 \\ 0{,}9 & 0 \\ 2{,}7 & 2 \\ 2{,}1 & 2 \\ 0{,}3 & 0 \\ 0{,}9 & 0 \\ 2{,}7 & 2 \\ 2{,}1 & 2 \\ \dots & \\ \end{array} \]

Stąd \((0{,}1)_{10} = (0{,}\underline{0022})_{3}\) .

Zapis liczb w komputerze

Liczby stałoprzecinkowe

Liczby stałoprzecinkowe (całkowite) są przechowywane w komputerze najczęściej w postaci ich reprezentacji binarnej. Nowoczesne języki pozwalają na używanie liczb stałoprzecinkowych o długościach 8, 16, 32 i 64 cyfr binarnych (czyli bitów). Tzw. liczby bez znaku to po prostu zapis liczby w postaci cyfr binarnych, tak jak robiliśmy to wyżej. Liczby ze znakiem są najczęściej przechowywane jako w tzw. kodzie uzupełnieniowym. Pokrótce go omówimy.

Dla ustalenia uwagi przyjmijmy, że chcemy przechowywać liczby \(n\) --bitowe ze znakiem. Nasza reprezentacja w kodzie uzupełnień będzie przechowywać liczby całkowite z przedziału \([-2^{n-1}, 2^{n-1}-1]\) (przedział nie jest symetryczny, zawiera jedną liczbę ujemną więcej niż dodatnią). Liczby dodatnie i zero są przechowywane dokładnie tak jak liczby bez znaku, w postaci liczby binarnej. Aby otrzymać reprezentację liczby ujemnej bierzemy reprezentację liczby przeciwnej, odwracamy wszystkie bity i dodajemy 1 do tak powstałej liczby binarnej. Dla przykładu przeanalizujmy to na liczbach czterobitowych. Znaczy to, że będziemy reprezentować liczby z przedziału \([-8,7]\) .

\[ \begin{align*} 0 &\longrightarrow 0000\\ 1 &\longrightarrow 0001\\ 2 &\longrightarrow 0010\\ 3 &\longrightarrow 0011\\ 4 &\longrightarrow 0100\\ 5 &\longrightarrow 0101\\ 6 &\longrightarrow 0110\\ 7 &\longrightarrow 0111\\ -1 &\longrightarrow 1111\\ -2 &\longrightarrow 1110\\ -3 &\longrightarrow 1101\\ -4 &\longrightarrow 1100\\ -5 &\longrightarrow 1011\\ -6 &\longrightarrow 1010\\ -7 &\longrightarrow 1001\\ -8 &\longrightarrow 1000\\ \end{align*} \]

Zaletą tej skomplikowanej na pierwszy rzut oka reprezentacji reprezentacji jest, że nie trzeba sprawdzać czy liczby są dodatnie czy ujemne przy dodawaniu. Po prostu wykonujemy operację tak jakbyśmy dodawali liczby dodatnie, pomijając ewentualny nadmiarowy bit. Wynik jest poprawny, chyba że nastąpi przepełnienie. Dla przykładu przy naszej czterobitowej reprezentacji:

\[ 7 + (-3) \longrightarrow 0111 + 1101 = 1 0100 \longrightarrow 0100 \longrightarrow 4 \]

Liczby zmiennoprzecinkowe

Liczby zmiennoprzecinkowe (ang. floating-point numbers) pozwalają na przechowywanie przybliżeń liczb rzeczywistych. Są szeroko stosowane w inżynierii, modelowaniu i grafice komputerowej. Liczby zmiennoprzecinkowe składają się ze znaku s , cechy c i mantysy m. Wartość liczby zmiennoprzecinkowej to \(s \cdot m \cdot 2^c\) . Cecha jest tak dobrana, by \(1 \leq m < 2\) . Zauważmy, że mantysa w zapisie binarnym jest ułamkiem z częścią całkowitą 1. Przy przechowywaniu mantysy 1 przed przecinkiem jest normalnie pomijane. Liczba zmiennoprzecinkowa jest przechowywana w pamięci w postaci ciągu bitów, najpierw bit znaku, potem bity cechy, następnie bity mantysy. Z reguły w ramach konkretnego formatu liczb zmiennoprzecinkowych ustalony jest tzw. nadmiar dla cechy, to znaczy liczba, którą należy odjąć aby otrzymać właściwą wartość cechy, do wpisania we wzorze powyżej.

Najczęściej spotykane typy zmiennoprzecinkowe to liczby pojedynczej precyzji (zajmuje w sumie 32 bity) i podwójnej precyzji (64 bity). Poniżej dla przykładu reprezentacje paru liczb w podwójnej precyzji (nadmiar dla cechy wynosi 1023):

\[ \begin{align*} 1.0 & \longrightarrow 0\, 01111111111\, 0000000000000000000000000000000000000000000000000000\\ -1.0 & \longrightarrow 1\, 01111111111\, 0000000000000000000000000000000000000000000000000000\\ 2.0 & \longrightarrow 0\, 10000000000\, 0000000000000000000000000000000000000000000000000000\\ 4.0 & \longrightarrow 0\, 10000000001\, 0000000000000000000000000000000000000000000000000000\\ 1.5 & \longrightarrow 0\, 01111111111\, 1000000000000000000000000000000000000000000000000000\\ 0.75 & \longrightarrow 0\, 01111111110\, 1000000000000000000000000000000000000000000000000000\\ 0.1 & \longrightarrow 0\, 01111111011\, 1001100110011001100110011001100110011001100110011010 \end{align*} \]

Te same liczby w pojedynczej precyzji:

\[ \begin{align*} 1.0 & \longrightarrow 0\, 01111111\, 00000000000000000000000\\ -1.0 & \longrightarrow 1\, 01111111\, 00000000000000000000000\\ 2.0 & \longrightarrow 0\, 10000000\, 00000000000000000000000\\ 4.0 & \longrightarrow 0\, 10000001\, 00000000000000000000000\\ 1.5 & \longrightarrow 0\, 01111111\, 10000000000000000000000\\ 0.75 & \longrightarrow 0\, 01111110\, 10000000000000000000000\\ 0.1 & \longrightarrow 0\, 01111011\, 10011001100110011001101 \end{align*} \]

Używane w komputerach formaty IEEE mogą też przyjmować wartości specjalne ( \(\pm 0, \pm \infty, \text{NaN}\) ) oraz mogą być tzw. liczbami subnormalnymi, czyli liczbami mniejszymi niż najmniejsza normalna liczba zmiennoprzecinkowa dodatnia, którą można przedstawić według opisanych wyżej zasad. Dla przykładu poniżej przykładowe wartości specjalne dla pojedynczej precyzji, w pierwszym wierszu najmniejsza dodatnia normalna liczba pojedynczej precyzji:

\[ \begin{align*} 1.1754943 \cdot 10^{-38} & \longrightarrow 0\, 00000001\, 00000000000000000000000\\ 1.1754942 \cdot 10^{-38} & \longrightarrow 0\, 00000000\, 11111111111111111111111\\ +0.0 & \longrightarrow 0\, 00000000\, 00000000000000000000000\\ -0.0 & \longrightarrow 1\, 00000000\, 00000000000000000000000\\ +\infty & \longrightarrow 0\, 11111111\, 00000000000000000000000\\ -\infty & \longrightarrow 1\, 11111111\, 00000000000000000000000\\ Nan & \longrightarrow 0\, 11111111\, 10000000000000000000000\\ \end{align*} \]

Zadanie 1. Znajdź resztę z dzielenia swojego numeru indeksu przez 15. Jeżeli wynikiem jest 0, 1 lub 2, dodaj do tak otrzymanej reszty 10. Jeżeli wynikiem jest 8, użyj liczby 7. Przedstaw swój numer indeksu w systemie o tak otrzymanej podstawie. (Np. 987646 mod 15 = 1, więc zadaniem jest przedstawienie 987646 w bazie 11). W przypadku konieczności użycia cyfr 10-15 użyj liter A-F.

Zadanie 2. Przestaw swój numer indeksu w bazie 2, 8 i 16.

Zadanie 3. Podaj wartość (dziesiętną) twojego numeru indeksu, jeśli przyjąć, że jest on liczbą zapisaną w systemie o podstawie 13.

Zadanie 4. Dokonaj konwersji ułamka \(0{,}xyz\) , gdzie \(xyz\) to trzy pierwsze cyfry twojego numeru indeksu z systemu dziesiętnego na binarny. Podaj osiem pierwszych cyfr po przecinku.

Zadanie 5. Dokonaj konwersji ułamka \(0{,}xyz\) , gdzie \(xyz\) to trzy ostatnie cyfry twojego numeru indeksu z systemu szesnastkowego na dziesiętny.

Rozwiązania proszę przesyłać w postaci jasno formatowanych plików tekstowych, plików PDF lub zdjęć/skanów ręcznie spisanych rozwiązań w sensownej jakości i wielkości (np. wysoka rozdzielczość, tryb 1-bitowy i kompresja CCITT). Proszę unikać formatu MS Word czy Open/LibreOffice. Lepiej konwertować je na końcu do PDF-a.