System uzupełnień do podstawy - U2

Dodawanie dwójkowe

Do wykonywania dodawania 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

 

System U2

Naturalny system dwójkowy (NBS - ang. Natural Binary System) pozwala przedstawiać jedynie liczby nieujemne. Dlatego do obliczeń komputerowych przyjęto nowy system, zwany systemem uzupełnień do podstawy 2 lub w skrócie U2 (ang. 2C - Two's Complement). W systemie 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 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 zapisie U2. Zauważ, iż w tym systemie wartość 0 ma tylko jedną reprezentację 0000, a 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 od 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, Amiga, Macintosh i innych, 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.

System uzupełnień do podstawy wymyślił znany francuski uczony Blaise Pascal. Otóż skonstruował on prostą maszynę arytmetyczną, która potrafiła dodawać liczby dziesiętne. Aby również umożliwić wykonywanie odejmowania, Pascal dodawał liczby uzupełnione do podstawy 10. Na przykład załóżmy, iż Pascal chciał wykonać odejmowanie 84 - 55. W tym celu tworzył uzupełnienie dziesiętne liczby 55, które dla liczb dwucyfrowych jest równe (dla 3 cyfrowych odejmujemy od 1000, dla n-cyfrowych odejmujemy od 10n) :
 

100 - 55 = 45


Otrzymaną liczbę dodawał na swojej maszynie do liczby 84 i dostawał wynik:
 

84 + 45 = 129
 

Ignorował najstarszą cyfrę, zatem pozostawało 29, a to jest wynik różnicy:
 

84 - 55 = 29
 

Sprytne, nieprawdaż? Zaletą tego systemu było to, iż uzupełnienie liczby można dosyć łatwo obliczać - sprawny rachmistrz może to robić nawet w pamięci. Na tej właśnie podstawie skonstruowany jest system U2 - uzupełnienie do podstawy 2.

 

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

 



List do administratora Serwisu Edukacyjnego I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo  , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

(C)2014 mgr Jerzy Wałaszek

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