![]() |
![]() ![]() ![]() ![]()
Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0 |
©2008 mgr
Jerzy Wałaszek |
Materiały rozszerzające
Maszyna licząca Pascala
System U2
Blaise Pascal jest powszechnie znanym fizykiem i matematykiem, który znacząco przyczynił się do rozwoju nauk przyrodniczych. Trochę mniej znany jest fakt, iż był on również konstruktorem maszyny liczącej zwanej Pascaliną (właściwie Pascal skonstruował 15 takich maszyn):
Pascalina była maszyną sumującą, tzn. potrafiła jedynie dodawać liczby. Z tego powodu Pascal wymyślił bardzo inteligentny sposób wykonywania na niej odejmowania. Załóżmy, iż operujemy tylko na liczbach dwucyfrowych. Chcemy wykonać odejmowanie 75 - 53. Robimy to tak:
Najpierw obliczamy tzw. uzupełnienie do 10 liczby ujemnej -53. Znajdujemy pierwszą potęgę 10, która jest większa od największej liczby dwucyfrowej - będzie to oczywiście 100 (gdybyśmy pracowali na liczbach 3 cyfrowych, byłoby to 1000, dla 4 cyfrowych - 10000, itd).
Do 100 dodajemy liczbę, której uzupełnienia szukamy:
100 + (-53) = 47
Rachunki są proste i sprawny rachmistrz może je z powodzeniem wykonać w pamięci.
Liczba 47 jest uzupełnieniem do 10 liczby -53.
Teraz odejmowanie realizujemy dodając uzupełnienie 47, zamiast liczby ujemnej -53:
75 + 47 = 122
Ponieważ operujemy na liczbach 2 cyfrowych, w otrzymanym wyniku pozostawiamy tylko dwie ostatnie cyfry, czyli 22.
Sprawdź sobie, iż 75 - 53 = 22.
Poznany wcześniej naturalny system dwójkowy (NBC - ang. Natural Binary Code) pozwalał kodować jedynie 0 oraz liczby całkowite dodatnie. W obliczeniach często musimy operować na liczbach ujemnych - zachodzi zatem problem, w jaki sposób reprezentować wartości ujemne i dodatnie za pomocą bitów, aby otrzymać spójny i praktyczny system liczbowy.
My rozwiązaliśmy to zadanie w swoim systemie dziesiętnym wprowadzając dodatkowy znak minus. Jednakże ten sposób nie nadaje się dla komputerów, ponieważ do dyspozycji są jedynie bity o stanach 0 lub 1. Musimy wymyślić coś innego. Tutaj właśnie przychodzi nam z pomocą Pascal wraz ze swoją maszyną i arytmetyką uzupełnieniową. Do reprezentacji liczb ujemnych Pascal wykorzystywał uzupełnienia do odpowiednich potęg podstawy systemu dziesiętnego - czyli liczby 10. W systemie binarnym naturalną rzeczą jest, iż będziemy tworzyć uzupełnienia do odpowiednich potęg podstawy systemu dwójkowego - czyli do 2.
Uzupełnienia są liczbami nieujemnymi - można je zatem kodować w naturalnym systemie binarnym, który już mamy. Musimy jedynie dokładnie określić sposób otrzymywania takich uzupełnień w systemie dwójkowym oraz interpretację bitów liczby uzupełnieniowej.
Zasada obliczania uzupełnienia do 2 jest następująca:
Niech n oznacza liczbę bitów liczby U2 a x jest wartością ujemną, którą da się przedstawić w systemie U2 na n bitach. Wartość uzupełnienia do 2 liczby x jest równa:
x = 2n + x
Otrzymany wynik x kodujemy w naturalnym systemie dwójkowym i otrzymujemy uzupełnienie do podstawy 2 liczby x.
Przykład:
Policzyć uzupełnienie do 2 wartości -3 dla 4 bitowej liczby U2:
n = 4
x = -3
x = 2n
+ x = 24 - 3 = 16 - 3 = 13 = 1101U2
Przykład:
Policzyć uzupełnienie do 2 wartości -102 dla 8 bitowej liczby U2:
n = 8
x = -102
x = 2n
+ x = 28 - 102 = 256 - 102 = 154
154 : 2 = 77 i reszta 0
77 : 2 = 38 i reszta 1
38 : 2 = 19 i reszta 0
19 : 2 = 9 i reszta 1
9 : 2 = 4 i reszta 1
4 : 2 = 2 i reszta 0
2 : 2 = 1 i reszta 0
1 : 2 = 0 i reszta 1
-102 = 10011010U2
Liczby dwójkowe w systemie U2 zostały wybrane do reprezentacji liczb całkowitych we współczesnych systemach komputerowych. Z tego powodu musimy znać ich własności. Pierwszą charakterystyczną cechą liczb U2 jest stały format, czyli liczba jest zawsze przedstawiana za pomocą ustalonej liczby bitów. Najczęściej jest to 8, 16, 32 lub 64 bity. Więcej bitów pozwala kodować większy zakres liczb.
Liczby dodatnie interpretujemy tak jak w naturalnym kodzie binarnym.
Przykład:
Niech liczba bitów liczby U2 wynosi 4. Wtedy:
0000U2 = 0
0001U2 = 1
0010U2 = 2
0011U2 = 2 + 1 = 3
0100U2 = 4
0101U2 = 4 + 1 = 5
0110U2 = 4 + 2 = 6
0111U2 = 4 + 2 + 1 = 7
Dla liczb ujemnych zauważamy, iż waga najstarszego bitu musi być ujemna - wtedy wartość liczby obliczamy wg znanego schematu, czyli suma wag pozycji, na których występuje cyfra 1.
Przykład:
1000U2 = -8, gdyż uzupełnienie jest równe 16 - 8 = 8 =
10002
1001U2 = -8 + 1 = -7, gdyż 16 - 7 = 9 = 10012
1010U2 = -8 + 2 = -6, gdyż 16 - 6 =10 = 10102
1011U2 = -8 + 2 + 1 = -5, gdyż 16 -5 = 11 = 10112,
itd.
Wynika stąd następujący wzór obliczeniowy:
LU2 = bn-1bn-2...b2b1b0 - zapis liczby U2
LU2 = bn-1(-2n-1) + bn-22n-2 + ... + b222 + b121 + b020
Wartość liczby U2 liczymy podobnie jak dla naturalnego kodu dwójkowego pamiętając jednakże, iż waga najstarszego bitu jest tutaj ujemna.
Przykład:
LU2 = 10011110U2
LU2 = (-27) + 24 + 23 + 22 + 21 = -128 + 16 + 8 + 4 + 2 = -128 + 30 = -98
Wzór ten wyjaśnia powód wprowadzenia stałego formatu (liczby bitów) dla liczb U2 - po prostu musimy wiedzieć, który z bitów będzie najstarszym, ponieważ posiada on wagę ujemną. Pozycja najstarszego bitu w liczbie U2 nosi nazwę pozycji znakowej. Zwróć uwagę, iż jeśli na tej pozycji jest cyfra 0, to liczba jest nieujemna - suma pozostałych wag jest zawsze albo równa 0, albo większa od 0. Jeśli na pozycji znakowej występuje cyfra 1, to liczba jest zawsze ujemna, ponieważ suma pozostałych wag jest zawsze mniejsza od wartości bezwzględnej wagi na starszej pozycji:
1111U2 = -8 + 4 + 2 + 1 = -1
Określimy zakres liczb możliwych do przedstawienia za pomocą n-bitowej liczby U2.
Najmniejszą wartość liczba U2 posiada wtedy, gdy na pozycji znakowej mamy cyfrę 1 (waga ujemna), a na wszystkich pozostałych pozycjach są cyfry 0. Zgodnie ze wzorem:
LU2 = bn-1(-2n-1) + bn-22n-2 + ... + b222 + b121 + b020
mamy:
bn-1 = 1, a pozostałe bity są równe zero, stąd
LU2min = -2n-1
Największą wartość liczba U2 przyjmuje wtedy, gdy pozycja znakowa zawiera cyfrę 0, a wszystkie pozostałe cyfry są równe 1:
bn-1 = 0
bn-2,....b2,b1,b0 = 1
LU2max = bn-22n-2 + ... + b222 + b121 + b020
Zauważamy, iż jest to maksymalna wartość (n-1) bitowej liczby w naturalnym kodzie dwójkowym. Wzór znamy z poprzedniej lekcji:
Dla n bitów liczba NBC przyjmuje największą wartość 2n - 1, zatem
dla n - 1 bitów liczba NBC przyjmie największą wartość 2n-1 - 1. Stąd:
LU2max = 2n-1 - 1
I ostatecznie zakres wartości n bitowej liczby U2 zawiera się w przedziale od -2n-1 do 2n-1 - 1
Przykład:
n |
zakres symbolicznie |
zakres liczbowo |
zakres bitowo |
1 | -20...20 - 1 | -1...0 | 1...0 |
2 | -21...21 - 1 | -2...1 | 10...01 |
3 | -22...22 - 1 | -4...3 | 100...011 |
4 | -23...23 - 1 | -8...7 | 1000...0111 |
8 | -27...27 - 1 | -128...127 | 1000000...01111111 |
16 | -215...215 - 1 | -32768...32767 | 1000000000000000...0111111111111111 |
Dla wprawy oblicz zakresy 32 i 64 bitowych liczb U2. Do przeprowadzenia rachunków możesz skorzystać z kalkulatora udostępnianego przez system Windows. Jest on wystarczająco dokładny.
Poniższy skrypt generuje różne liczby całkowite i żąda zapisania ich w kodzie U2 o podanym formacie. Przy jego pomocy możesz sprawdzić swoje obliczenia. Zagwarantowane jest, iż daną liczbę można przedstawić w kodzie U2 o wymaganym formacie.
![]() | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe