Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja 1.0

©2008 mgr Jerzy Wałaszek I LO w Tarnowie

Liczby całkowite - kod uzupełnień do 2 - U2

Materiały rozszerzające

Maszyna licząca Pascala
System U2

Pascalina

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.

Obliczanie uzupełnień do 2

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 = 2ⁿ  + 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 = 2ⁿ  + x  = 2⁴ - 3 = 16 - 3 = 13 = 1101_U2

Przykład:

Policzyć uzupełnienie do 2 wartości -102 dla 8 bitowej liczby U2:

n  = 8
x  = -102
x = 2ⁿ  + x  = 2⁸ - 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 = 10011010_U2

Obliczanie wartości liczb U2

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:

0000_U2 = 0
0001_U2 = 1
0010_U2 = 2
0011_U2 = 2 + 1 = 3
0100_U2 = 4
0101_U2 = 4 + 1 = 5
0110_U2 = 4 + 2 = 6
0111_U2 = 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:

1000_U2 = -8, gdyż uzupełnienie jest równe 16 - 8 = 8 = 1000₂
1001_U2 = -8 + 1 = -7, gdyż 16 - 7 = 9 = 1001₂
1010_U2 = -8 + 2 = -6, gdyż 16 - 6 =10 = 1010₂
1011_U2 = -8 + 2 + 1 = -5, gdyż 16 -5 = 11 = 1011₂, itd.

Wynika stąd następujący wzór obliczeniowy:

L_U2 = b_n-1b_n-2...b₂b₁b₀ - zapis liczby U2

L_U2 = b_n-1(-2^n-1) + b_n-22^n-2 + ... + b₂2² + b₁2¹ + b₀2⁰

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:

L_U2 = 10011110_U2

L_U2 = (-2⁷) + 2⁴ + 2³ + 2² + 2¹ = -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:

1111_U2 = -8 + 4 + 2 + 1 = -1

Zakres liczb U2

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:

L_U2 = b_n-1(-2^n-1) + b_n-22^n-2 + ... + b₂2² + b₁2¹ + b₀2⁰

mamy:

b_n-1 = 1, a pozostałe bity są równe zero, stąd

L_U2min = -2^n-1

Największą wartość liczba U2 przyjmuje wtedy, gdy pozycja znakowa zawiera cyfrę 0, a wszystkie pozostałe cyfry są równe 1:

b_n-1 = 0
b_n-2,....b₂,b₁,b₀ = 1

L_U2max = b_n-22^n-2 + ... + b₂2² + b₁2¹ + b₀2⁰

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ść 2ⁿ - 1, zatem

dla n - 1 bitów liczba NBC przyjmie największą wartość 2^n-1 - 1. Stąd:

L_U2max = 2^n-1 - 1

I ostatecznie zakres wartości n bitowej liczby U2 zawiera się w przedziale od -2^n-1 do 2^n-1 - 1

Przykład:

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.

Ćwiczenie

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    im. Kazimierza Brodzińskiego w Tarnowie ©2023 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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