Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych Autor artykułu: mgr Jerzy Wałaszek |
©2014 mgr
Jerzy Wałaszek
|
Do wykonywania dodawania dwójkowego (ang. binary addition) niezbędna jest znajomość tabliczki dodawania, czyli wyników sumowania każdej cyfry z każdą inną. W systemie binarnym mamy tylko dwie cyfry 0 i 1, zatem tabliczka dodawania jest niezwykle prosta i składa się tylko z 4 pozycji:
0 + 0 = | 0 |
0 + 1 = | 1 |
1 + 0 = | 1 |
1 + 1 = | 10 |
Przykład:
Zsumować liczby binarne 1111001(2) oraz 10010(2).
1111001 | |
+ | 10010 |
1111001 | |
+ | 10010 |
1011 |
1 | |||||||
1 | 1 | 1 | 1 | 0 | 0 | 1 | |
+ | 1 | 0 | 0 | 1 | 0 | ||
0 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | |||||
1 | 1 | 1 | 1 | 0 | 0 | 1 | |
+ | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
0 | 0 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | ||||||
0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | |
+ | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
1111001(2) + 10010(2) = 10001011(2) (121 + 18 = 139)
Oto kilka dalszych przykładów:
|
|
|
Uwaga, pułapka:W pamięci komputera liczby binarne przechowywane są w postaci ustalonej ilości bitów (np. 8, 16, 32 bity). Jeśli wynik sumowania np. dwóch liczb 8 bitowych jest większy niż 8 bitów, to najstarszy bit (dziewiąty bit) zostanie utracony. Sytuacja taka nazywa się nadmiarem (ang. overflow) i występuje zawsze, gdy wynik operacji arytmetycznej jest większy niż górny zakres danego formatu liczb binarnych (np. dla 8 bitów wynik większy od 28 - 1, czyli większy od 255):
11111111(2) + 00000001(2) = 1|00000000(2) (255 + 1 = 0)
Przy nadmiarze otrzymany wynik jest zawsze błędny. |
Na poprzedniej lekcji poznaliśmy szczegółowo naturalny system binarny NBC (ang. Natural Binary Code). Jest on niezmiernie ważny dla informatyka, ponieważ stanowi punkt wyjścia dla większości innych systemów kodowania liczb. Jednakże NBC pozwala zapisywać tylko liczby dodatnie oraz liczbę zero. W przypadku liczb ujemnych mamy problem. W tym momencie większość uczniów podrapie się za uchem i odpowie - jaki tam znowu problem, po prostu dopisujemy przed liczbą znak minus i załatwione, na przykład:
-101(2) = -5(10).
Super. Ale tak można zrobić jedynie na papierze. Liczby binarne muszą być umieszczane w pamięci komputera, a tam mamy tylko bity, czyli symbole 0 lub 1. Żaden bit nie przyjmuje dodatkowego stanu '-'. Mamy zatem problem. A problem ten sprowadza się do wymyślenia takiego sposobu kodowania, aby za pomocą bitów można było zapisywać wartości ujemne.
O ile system NBC był swobodny co do ilości bitów w zapisie liczby, to systemy kodowania liczb ze znakiem posiadają ściśle ustalone formaty, tzn. ilość bitów w zapisie liczby jest określona na stałe (8b, 16b, 32b, 64b itd.). Jest to konieczne, ponieważ zwykle najstarszy bit posiada inne znaczenie od pozostałych bitów liczby (nazywany jest on często bitem znaku - ang. sign bit) i musimy znać jego położenie, aby prawidłowo zinterpretować wartość liczby.
System kodowania liczb ze znakiem nazywany jest systemem uzupełnień do podstawy 2 lub w skrócie U2 (ang. 2C - Two's Complement). W systemie U2 wagi pozycji dwójkowych są takie same jak w NBS, z wyjątkiem najstarszej pozycji, która jest ujemna. Bit na tej pozycji nosi nazwę bitu znakowego (ang. sign bit).
Wartości wag pozycji w zapisie U2 | |||||||
---|---|---|---|---|---|---|---|
waga | -2n-1 | 2n-2 | 2n-3 | 22 | 21 | 20 | |
cyfra | bn-1 | bn-2 | bn-3 | ... | b2 | b1 | b0 |
Liczba jest dodatnia, gdy bit znaku ma wartość 0 - suma pozostałych wag tworzy zawsze liczbę dodatnią lub zero. Jeśli bit znaku przyjmie wartość 1, to liczba jest ujemna.
Zapamiętaj:Wartość liczby U2
obliczamy tak samo jak w systemie NBS - cyfry mnożymy przez wagi
pozycji, na których się znajdują i dodajemy otrzymane iloczyny.
Waga bitu znakowego jest ujemna. bn-1bn-2bn-3...b2b1b0 (U2) = bn-1(-2n-1) + bn-22n-2 + bn-32n-3 + ... + b222 + b121 + b020 gdzie b - bit, cyfra dwójkowa 0 lub 1 |
4 bitowy system U2 | ||
---|---|---|
Kod U2 | Przeliczenie | Wartość |
0000 | 0 | 0 |
0001 | 20 | 1 |
0010 | 21 | 2 |
0011 | 21 + 20 | 3 |
0100 | 22 | 4 |
0101 | 22 + 20 | 5 |
0110 | 22 + 21 | 6 |
0111 | 22 + 21 + 20 | 7 |
1000 | (-23) | (-8) |
1001 | (-23) + 20 | (-7) |
1010 | (-23) + 21 | (-6) |
1011 | (-23) + 21 + 20 | (-5) |
1100 | (-23) + 22 | (-4) |
1101 | (-23) + 22 + 20 | (-3) |
1110 | (-23) + 22 + 21 | (-2) |
1111 | (-23) + 22 + 21 + 20 | (-1) |
Ponieważ w systemach binarnych cyfry przyjmują tylko dwie wartości 0 lub 1, można rachunek znacznie uprościć sumując jedynie te wagi, dla których cyfra zapisu liczby ma wartość 1.
W tabelce obok zebraliśmy wszystkie możliwe do utworzenia 4-bitowe liczby w kodzie U2. Zauważ, iż w tym systemie liczb ujemnych jest o 1 więcej niż dodatnich (-8 .. -1, 1 .. 7). Najstarszy bit określa znak liczby. Jeśli jest równy 0, liczba jest dodatnia i resztę zapisu możemy potraktować jak liczbę w naturalnym kodzie dwójkowym.
Przykład:
01101011(U2) = 64 + 32 + 8 + 2 + 1 = 107(10). |
Jeśli bit znaku ustawiony jest na 1, to liczba ma wartość ujemną. Bit
znaku ma wagę
Przykład:
11101011(U2) = (-27) + 64 + 32 + 8 + 2 + 1 = -128 + 107 = (-21)(10). |
Liczbę przeciwną do danej liczby U2 uzyskujemy na dwa sposoby:
Zapamiętaj:Sposób 1 - procedura wyznaczania liczby
przeciwnej w kodzie U2
|
Przykład:
Wyznaczyć liczbę przeciwną w kodzie U2 do danej liczby 01101110(U2).
NOT | 01101110 |
10010001 |
10010001 | |
+ | 00000001 |
10010010 |
Liczbą przeciwną do 01101110(U2) jest 10010010(U2).
Aby się o tym przekonać, obliczmy wartości dziesiętne obu liczb:
01101110(U2) = 64 + 32 + 8 + 4 + 2 = 110(10).
10010010(U2) = (-128) + 16 + 2 = (-128) + 18 = (-110)(10).
Zwróć uwagę, iż tym sposobem nie da się otrzymać liczby przeciwnej do najmniejszej liczby ujemnej (bit znaku ustawiony na 1, a wszystkie pozostałe bity równe 0). Na przykład dla 4 bitowego kodu U2 otrzymujemy:
(-8)(10) = 1000(U2) ; NOT(1000) = 0111; 0111 + 0001 = 1000, a to jest ta sama liczba wyjściowa.
Oczywistym wyjaśnieniem tego faktu jest to, iż najmniejsza w danym formacie U2 liczba ujemna nie posiada w tym formacie swojego odpowiednika po stronie dodatniej, gdyż suma wszystkich wag dodatnich jest o 1 mniejsza od modułu wagi ujemnej bitu znakowego.
Zapamiętaj:Sposób 2 - procedura wyznaczania liczby
przeciwnej w kodzie U2
|
Ten drugi sposób jest o wiele prostszy, ponieważ nie wymaga od nas dodawania. Możemy go zastosować prawie bezmyślnie do dowolnie długich liczb U2.
Przykład:
Znaleźć liczbę przeciwną w kodzie U2 do danej liczby 1100100010111010111010010100001000000(U2). Bez paniki, pokażemy w kolejnych krokach, jak to zadanie wykonać:
Liczba U2 | 1100100010111010111010010100001000000 |
---|---|
Liczba przeciwna U2 | 000000 |
Liczba U2 | 1100100010111010111010010100001000000 |
---|---|
Liczba przeciwna U2 | 1000000 |
Liczba U2 | 1100100010111010111010010100001000000 |
---|---|
Liczba przeciwna U2 | 0011011101000101000101101011111000000 |
Również drugi sposób zawodzi przy wyznaczaniu liczby przeciwnej do najmniejszej liczby ujemnej w danym formacie U2. Dlatego na wartość tę należy zwrócić szczególną uwagę.
Dla liczb dodatnich nie ma problemu z przeliczaniem na kod U2. Wystarczy znaleźć reprezentację dwójkową danej wartości liczbowej, a następnie uzupełnić ją bitami 0 do długości formatu kodu U2.
Przykład:
Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej 27(10).
27(10) = 16 + 8 + 2 + 1 = 11011(2) = 00011011(U2).
W przypadku wartości ujemnej mamy kilka możliwości postępowania, które opisujemy poniżej.
Zapamiętaj:Sposób 1 - przeliczanie ujemnej liczby dziesiętnej na liczbę U2 Liczba ujemna musi mieć ustawiony na 1 bit znaku.
Zatem nasze zadanie sprowadza się do znalezienia wartości
pozostałych bitów. Bit znaku stoi na pozycji o wadze
kodowana liczba = waga bitu znakowego + wartość kodu pozostałych bitów kodowana liczba = (-2n-1) + wartość kodu pozostałych bitów stąd wartość kodu pozostałych bitów = 2n-1 + kodowana liczba
Po wyznaczeniu wartości tego kodu tworzymy jego zapis w systemie dwójkowym, uzupełniamy w miarę potrzeby bitem 0 do długości formatu U2 - 1 i dodajemy bit znakowy 1. Konwersja jest gotowa. |
Przykład:
Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej (-45)(10).
Wyznaczamy moduł wagi pozycji znakowej. Dla n = 8, 2n-1 = 27 = 128 wartość kodu pozostałych bitów = 128 + (-45) = 83 = 1010011(2)
Dodajemy bit znaku równy 1 i otrzymujemy:
(-45)(10) = 11010011(U2).
Zapamiętaj:Sposób 2 - przeliczanie
ujemnej liczby dziesiętnej na liczbę U2
|
Przykład:
Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej (-45)(10).
Wyznaczamy kod binarny liczby przeciwnej: 45(10) = 101101(2)
Kod uzupełniamy dwoma bitami 0 do wymaganej długości 8 bitów: 00101101.
Wyznaczamy liczbę przeciwną wg drugiej metody: 00101101(U2) : 11010011(U2).
Stąd (-45)(10) = 11010011(U2).
Zapamiętaj:Sposób 3 - przeliczanie ujemnej liczby dziesiętnej na zapis U2 Jeśli do liczby 2n (n - ilość bitów w formacie U2) dodamy przetwarzaną liczbę dziesiętną, to w wyniku otrzymamy wartość kodu dwójkowego równoważnego bitowo (tzn. o takiej samej postaci) kodowi U2 przetwarzanej liczby. Wynik dodawania wystarczy zapisać w postaci naturalnego kodu dwójkowego i konwersja jest zakończona. |
Przykład:
Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej (-45)(10).
28 + (-45) = 256 - 45 = 211 = 11010011(2).
Stąd
(-45)(10) = 11010011(U2).
Największa liczba U2 powstaje dla bitu znaku równego 0, a pozostałych bitów równych 1. Ponieważ pozostałe bity przedstawiają wartość w naturalnym kodzie binarnym i jest ich n-1, to
max(U2) = 2n-1 - 1
Z kolei najmniejszą wartość liczby U2 otrzymamy dla bitu znaku równego 1, a pozostałych bitów równych 0. W tym przypadku wartość liczby jest równa wadze pozycji znakowej, czyli
min(U2) = (-2n-1)
Zapamiętaj:Zakres n bitowej liczby w kodzie U2 wynosi
Z(U2) = -2n-1 ... 2n-1 - 1
Zakres liczb U2 jest niesymetryczny - liczb ujemnych jest o jedną więcej niż liczb dodatnich. |
Przykład:
4 bitowe liczby U2 posiadają zakres:
od | -23 | = | -8 | = 1000(U2) |
do | 23 - 1 | = | 7 | = 0111(U2) |
8 bitowe liczby U2 posiadają zakres:
od | -27 | = | -128 | = 10000000(U2) |
do | 27 - 1 | = | 127 | = 01111111(U2) |
16 bitowe liczby U2 posiadają zakres:
od | -215 | = | -32768 | = 1000000000000000(U2) |
do | 215 - 1 | = | 32767 | = 0111111111111111(U2) |
System zapisu U2 liczb ze znakiem jest dzisiaj powszechnie stosowany we wszystkich komputerach IBM, ponieważ jego arytmetyka jest bardzo zbliżona do arytmetyki liczb w naturalnym kodzie binarnym. Dzięki temu procesory mogą wykonywać operacje arytmetyczne na liczbach NBC i U2 za pomocą tych samych układów elektronicznych. A to przekłada się bezpośrednio na pieniążki - niższe koszty opracowania i produkcji procesorów.
Liczby U2 dodajemy wg poznanych zasad dla naturalnego systemu dwójkowego. Przeniesienia poza bit znaku ignorujemy (w rzeczywistości takie przeniesienia czy pożyczki mogą być wykorzystywane przez procesor do dodawania liczb o tzw. wielokrotnej precyzji).
Przykład:
3 + 3
|
5 + (-4)
|
(-3) + (-2)
|
W trakcie wykonywania działań arytmetycznych wynik operacji może przekroczyć dozwolony zakres liczb zarówno powyżej górnej granicy (nadmiar - ang. overflow) jak i poniżej dolnej (niedomiar - ang. underflow). Cechą charakterystyczną nadmiaru/niedomiaru jest zmiana znaku wyniku w sytuacji, gdy nie powinna ona nastąpić. Załóżmy, iż operujemy na 4 bitowych liczbach w kodzie U2 i chcemy wykonać proste dodawanie:
0 111 + 0 001 |
7 + 1 |
|
1 000 | -8 |
Otrzymany wynik jest niepoprawny w tym kodzie. Spowodowane to jest tym, iż liczba 8 będąca sumą 7 i 1 wykracza poza górny zakres wartości 4 bitowego kodu U2 (równy 7) i nie można jej poprawnie przedstawić - musielibyśmy przeznaczyć na zapis liczby więcej bitów.
Podobną sytuację zastaniemy przy próbie dodania dwóch liczb ujemnych, np. -6 i -3:
1 010 + 1 101 |
-6 + -3 |
|
10 111 | 7 |
Liczba -9 jest mniejsza od dolnego krańca 4 bitowych liczb w kodzie U2 (równego -8) i z tego powodu nie może być poprawnie przedstawiona w tym kodzie.
Zapamiętaj:Wystąpienie nadmiaru lub niedomiaru jest wskazówką dla programisty, iż źle dobrał typ danych dla przetwarzanej informacji - liczby są reprezentowane zbyt małą ilością bitów i nie można poprawnie zapisywać wyniku operacji. Najprostszym rozwiązaniem będzie zwiększenie długości formatu U2 (np. z 16 bitów na 32 bity). |
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