Informatyka dla klas II

Liczby bez znaku i ze znakiem

Dodawanie dwójkowe

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).

  1. Sumowane liczby zapisujemy jedna pod drugą, tak aby w kolejnych kolumnach znalazły się cyfry stojące na pozycjach o tych samych wagach (identycznie postępujemy w systemie dziesiętnym zapisując liczby w słupkach przed sumowaniem):
  1111001
+  10010

 

  1. Sumowanie rozpoczynamy od ostatniej kolumny. Sumujemy cyfry w kolumnie zgodnie z podaną tabelką zapisując wynik pod kreską:
  1111001
+  10010
  1011

 

  1. Jeśli wynik sumowania jest dwucyfrowy (1 + 1 = 10), to pod kreską zapisujemy tylko ostatnią cyfrę 0, a 1 przechodzi do następnej kolumny - dodamy ją do wyniku sumowania cyfr w następnej kolumnie. Jest to tzw. przeniesienie (ang. carry). Przeniesienie zaznaczyliśmy na czerwono:
    1          
  1 1 1 1 0 0 1
    1 0 0 1 0
      0 1 0 1 1

 

  1. Jeśli w krótszej liczbie zabrakło cyfr, to dopisujemy zera. Pamiętajmy o przeniesieniach.
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. Dodaliśmy wszystkie cyfry, ale przeniesienie wciąż wynosi 1. Zatem dopisujemy je do otrzymanego wyniku (możemy potraktować pustą kolumnę tak, jakby zawierała cyfry 0 i do wyniku sumowania dodać przeniesienie).
  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:

  1 1 1 1 1 1 1  
  0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1
  1 0 0 0 0 0 0 0
  1 1 1 1 1 1 1  
  0 1 1 1 1 1 1 1
0 0 0 0 0 1 0 1
  1 0 0 0 0 1 0 0
    1 1 1 1      
  1 0 1 1 1 1 1 0
0 0 0 0 1 1 0 0
  1 1 0 0 1 0 1 0

 

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.

 

System U2

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
n - liczba bitów w zapisie liczby

 

 

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ę (-2n-1), gdzie n  oznacza liczbę bitów w wybranym formacie U2. Reszta bitów jest zwykłą liczbą w naturalnym kodzie dwójkowym. Wagę bitu znakowego i wartość pozostałych bitów sumujemy otrzymując wartość liczby U2:

 

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
  1. Dokonać negacji wszystkich bitów zapisu liczby U2.
  2. Do wyniku dodać 1.

 

Przykład:

Wyznaczyć liczbę przeciwną w kodzie U2 do danej liczby 01101110(U2).

  1. Dokonujemy negacji (zmianę na wartości przeciwne) wszystkich bitów liczby U2:
NOT    01101110
  10010001

 

  1. Do wyniku negacji dodajemy 1:
  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
  1. Przejść do pierwszego od prawej strony bitu zapisu liczby.
  2. Do wyniku przepisać kolejne bity 0, aż do napotkania bitu o wartości 1, który również przepisać.
  3. Wszystkie pozostałe bity przepisać zmieniając ich wartość na przeciwną.

 

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ć:

  1. Analizę liczby rozpoczynamy od ostatniej cyfry zapisu liczby. Przesuwamy się w lewą stronę. Do wyniku przepisujemy wszystkie kolejne bity o wartości 0, aż do napotkania bitu 1.
Liczba U2 1100100010111010111010010100001000000
Liczba przeciwna U2 000000

 

  1. Napotkany bit 1 również przepisujemy do wyniku bez zmian:
Liczba U2 1100100010111010111010010100001000000
Liczba przeciwna U2 1000000

 

  1. Pozostałe bity przepisujemy zmieniając ich stan na przeciwny. To wszystko.
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ę.

 

Przeliczanie liczb dziesiętnych na liczby U2

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 (-2n-1), n - ilość bitów w formacie U2. Pozostałe bity zapisu liczby tworzą naturalny kod dwójkowy. Wartość tego kodu musi być taka, aby po dodaniu jej do wagi pozycji znakowej otrzymać wartość kodowanej liczby. Zapiszmy to w formie równania:

 

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
  1. Wyznaczamy zapis dwójkowy liczby przeciwnej (czyli dodatniej).
  2. Otrzymany kod dwójkowy uzupełniamy w miarę potrzeb do rozmiaru formatu U2.
  3. Wyznaczamy liczbę przeciwną za pomocą jednej z opisanych wcześniej metod

 

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).

 

Zakres n bitowych liczb 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)

 

Dodawanie liczb 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
  0011
+  0011
  0110
6
    5 + (-4)
  0101
+  1100
1 0001
1
    (-3) + (-2)
  1101
+  1110
1 1011
(-5)
   

 

Nadmiar i niedomiar w kodzie U2

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   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 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