Zapis uzupełnień do 2 - U2

System zapisu U1 przedstawiony w poprzednim rozdziale umożliwiał w prosty sposób kodowanie liczb ujemnych. Jednakże wykonywanie operacji arytmetycznych wciąż wymagało dodatkowych założeń - przy dodawaniu do wyniku należało dodać przeniesienie poza bit znaku, aby otrzymać poprawny wynik.

Okazuje się, iż drobna modyfikacja systemu U1 pozwala ominąć te wady. W tym celu zmieniamy wagę bitu znakowego z (-2^n-1 + 1) na (-2^n-1), gdzie n oznacza ilość bitów w formacie kodu. Wagi stają się teraz jednorodne - bit znakowy posiada wagę ujemną, lecz o wartości bezwzględnej takiej samej jak w naturalnym kodzie dwójkowym. Nowy kod nosi nazwę uzupełnień do podstawy 2 lub w skrócie U2 (ang. 2C - Two's Complement).

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.

		Wartość dziesiętna liczby w zapisie U2 Wartość liczby U2 obliczamy zgodnie z poznanymi zasadami - 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

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-ro bitowe liczby w zapisie U2. Zauważ, iż w przeciwieństwie do poprzednio opisanych systemów ZM i U1 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.

01101011_(U2) = 64 + 32 + 8 + 2 + 1 = 107₍₁₀₎.

Jeśli bit znaku ustawiony jest na 1, to liczba ma wartość ujemną. Bit znaku ma wagę (-2^n-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:

11101011_(U2) = (-2⁷) + 64 + 32 + 8 + 2 + 1 = -128 + 107 = (-21)₍₁₀₎.

Zwróć uwagę, iż postać ujemna liczby U2 nie jest już tak czytelna dla nas jak w przypadku kodów ZM (tylko zmiana bitu znaku) i U1 (negacja wszystkich bitów).

Liczbę przeciwną do danej liczby U2 uzyskujemy na dwa sposoby:

		Sposób 1 - procedura wyznaczania liczby przeciwnej w kodzie U2 Dokonać negacji wszystkich bitów zapisu liczby U2. Do wyniku dodać 1.

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₍₁₀₎.
10010010_(U2) = (-128) + 16 + 2 = (-128) + 18 = (-110)₍₁₀₎.

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)₍₁₀₎ = 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.

		Sposób 2 - procedura wyznaczania liczby przeciwnej w kodzie U2 Przejść do pierwszego od prawej strony bitu zapisu liczby. Do wyniku przepisać kolejne bity 0, aż do napotkania bitu o wartości 1, który również przepisać. 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.

 

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

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.

 

Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej 27₍₁₀₎.

27₍₁₀₎ = 16 + 8 + 2 + 1 = 11011₍₂₎ = 00011011_(U2).

W przypadku wartości ujemnej mamy kilka możliwości postępowania, które opisujemy poniżej.

		Sposób 1 - przeliczanie ujemnej liczby dziesiętnej na zapis 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.

 

Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej (-45)₍₁₀₎.

Wyznaczamy moduł wagi pozycji znakowej. Dla n = 8, 2^n-1 = 2⁷ = 128

wartość kodu pozostałych bitów = 128 + (-45) =  83 = 1010011₍₂₎

Dodajemy bit znaku równy 1 i otrzymujemy:

(-45)₍₁₀₎ = 11010011_(U2).

		Sposób 2 - przeliczanie ujemnej liczby dziesiętnej na zapis U2 Wyznaczamy zapis dwójkowy liczby przeciwnej (czyli dodatniej). Otrzymany kod dwójkowy uzupełniamy w miarę potrzeb do rozmiaru formatu U2. Wyznaczamy liczbę przeciwną za pomocą jednej z opisanych wcześniej metod.

 

Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej (-45)₍₁₀₎.

Wyznaczamy kod binarny liczby przeciwnej: 45₍₁₀₎ = 101101₍₂₎

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)₍₁₀₎ = 11010011_(U2).

		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.

 

Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej (-45)₍₁₀₎.

2⁸ + (-45) = 256 - 45 = 211 = 11010011₍₂₎.

Stąd (-45)₍₁₀₎ = 11010011_(U2). Jak widać, jest to metoda najszybsza z opisanych. Polecam!

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) = 2^n-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) = (-2^n-1)

		Zakres n bitowej liczby w kodzie U2 wynosi Z(U2) = (-2n-1, 2n-1 - 1) W porównaniu z systemami ZM i U1, zakres liczb U2 jest niesymetryczny - liczb ujemnych jest o jedną więcej niż liczb dodatnich.

 

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)

Zapis U2, podobnie jak opisane wcześniej zapisy NBC, ZM i U1, można rozszerzyć do zapisu stałoprzecinkowego dodając bity o wagach ułamkowych równych olejnym, ujemnym potęgom podstawy 2. Zasada obliczania wartości liczby stałoprzecinkowej U2 w niczym nie różni się od poprzednio opisanych zasad - jeśli uważnie przeczytałeś do tego miejsca nasz artykuł, to nie będziesz miał z tym żadnych problemów. Jeśli nie, cóż, informatyka na pewno nie jest dziedziną dla leniwych...

 

0110,1011_(U2) = 2² + 2¹ + 2^-1 + 2^-3 + 2^-4
0110,1011_(U2) = 4 + 2 + ¹/₂ + ¹/₈ + ¹/₁₆
0110,1011_(U2) = 6 ¹¹/₁₆

1101,0011_(U2) = (-2³) + 2² + 2⁰ + 2^-3 + 2^-4
1101,0011_(U2) = (-8) + 4 + 1 + ¹/₈ + ¹/₁₆
1101,0011_(U2) = (-8) + 5 ³/₁₆
1101,0011_(U2) = -(2 ¹³/₁₆)

Jeśli chcemy wyznaczyć liczbę przeciwną do danej liczby stałoprzecinkowej w kodzie U2, to stosując pierwszą z opisanych powyżej metod zamiast 1 do zanegowanych bitów dodajemy liczbę stałoprzecinkową z ustawionym na 1 bitem na najmłodszej pozycji.

 

Obliczamy liczbę przeciwną do 1101,1001_(U2) = (-2 ⁷/₁₆)

NOT	1101,1001	= 2 7/16
	0010,0110
+	0000,0001
	0010,0111

Druga metoda nie wymaga modyfikacji. Idziemy od końca zapisu liczby i przepisujemy wszystkie bity zerowe, aż do napotkania bitu 1. Bit ten przepisujemy bez zmian, a wszystkie pozostałe przepisujemy ze stanem przeciwnym:

 

Obliczamy liczbę przeciwną do 0001,1100_(U2) = 1 ³/₄

0001,1100	= -1 3/4
00
100
1110,0100

Wartość dziesiętną przeliczamy na zapis stałoprzecinkowy U2 wg następujących zasad:

1. Jeśli liczba jest dodatnia, to stosujemy dowolną z opisanych wcześniej metod w celu wyznaczenia jej reprezentacji binarnej. Wynik musimy jednak uzupełnić bitami 0 do długości wybranego formatu U2.

 

Znaleźć zapis U2 liczby 3,125. Zapis U2 posiada 4 bity całkowite i 4 bity ułamkowe:

3₍₁₀₎ = 11₍₂₎ - część całkowita

0,125₍₁₀₎ = ¹/₈ = 0,001₍₂₎ - część ułamkowa

Łączymy obie części w całość i uzupełniamy odpowiednio bitami 0 do wymagań formatu U2:

3,125₍₁₀₎ = 11,001₍₂₎ = 0011,0010_(U2).

1. Jeśli liczba jest ujemna, to jej zapis U2 możemy znaleźć na kilka sposobów. Na przykład można obliczyć zapis binarny liczby przeciwnej do niej (czyli dodatniej), uzupełnić bitami 0, a następnie zamienić otrzymany od U2 na liczbę przeciwną. Jednakże proponuję bardzo prostą metodę, która bezpośrednio pozwala wyznaczyć kod binarny liczby U2. Jeśli zapis U2 posiada n cyfr całkowitych, to liczbę wyjściową sumujemy z wartością 2ⁿ. W wyniku otrzymujemy wartość naturalnego kodu dwójkowego, który bitowo jest równoważny kodowi U2 przeliczanej liczby.

 

Znaleźć zapis U2 liczby -2,125. Zapis U2 posiada 3 bity całkowite oraz 5 bitów ułamkowych.

Ponieważ bitów całkowitych jest n=3, to liczbę -2,125 sumujemy z liczbą 2³ = 8:

8 + (-2,125) = 5,875 = 5 ⁷/₈

Otrzymana wartość zamieniamy na liczbę w naturalnym kodzie binarnym, po czym uzupełniamy bitami 0 do specyfikacji formatu U2:

5,875₍₁₀₎ = 101,111₍₂₎ = 101,11100

Otrzymany kod jest stałoprzecinkowym kodem U2 liczby wyjściowej:

-2,125₍₁₀₎ = 101,11100_(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 10ⁿ) :

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.

Dodawanie i odejmowanie

Liczby U2 dodajemy i odejmujemy 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).

3 + 3   0011 +  0011   0110 6

5 + (-4)   0101 +  1100 1 0001 1

(-3) + (-2)   1101 +  1110 1 1011 (-5)

5 - 4   0101 -  0100   0001 1

(-2) - 3   1110 -  0011   1011 (-5)

(-7) - (-6)   1001 -  1010 1 1111 (-1)

Mnożenie

Mnożenie liczb w kodzie U2 różni się nieco od standardowego mnożenia liczb binarnych. Przed wykonaniem tej operacji arytmetycznej musimy rozszerzyć znakowo obie mnożone liczby tak, aby ich długość (liczba bitów) wzrosła dwukrotnie (jeśli są różnej długości, to rozszerzamy znakowo względem dłuższej liczby). Rozszerzenie znakowe polega na powielaniu bitu znaku na wszystkie dodane bity. Np.:

0111_(U2) = 0000 0111_(U2) - rozszerzyliśmy znakowo liczbę 4 bitową do 8 bitowej
1011_(U2) = 1111 1011_(U2) - to samo dla liczby ujemnej.

Rozszerzenie znakowe nie zmienia wartości liczby w kodzie U2. Po wykonaniu rozszerzenia znakowego liczby mnożymy standardowo.

 

Pomnóżmy (-2) x 3:

-2 = 1110_(U2) = 1111 1110_(U2)
  3 = 0011_(U2) = 0000 0011_(U2)

(-2) x 3 11111110  x   00000011

011111110 +  111111100

1011111010 -6

Wynik mnożenia może być liczbą o długości równej sumie długości mnożonych liczb. Dlatego bity wykraczające w naszym przykładzie poza 8 bitów ignorujemy. Pozostałe 8 bitów określa w kodzie U2 liczbę -6. Zatem rachunek zgadza się.

Dzielenie

Najprostszym rozwiązaniem jest zapamiętanie znaków dzielonych liczb, zamiana ich na liczby dodatnie, dokonanie dzielenia dla liczb naturalnych, a następnie zmiana znaku wyniku, jeśli znaki dzielnej i dzielnika różnią się.

Podzielmy 6 przez -3:

 6 = 0110_(U2)
-3 = 1101_(U2) - zmieniamy na 3 = 0011_(U2)

Dzielimy liczbę 0110 przez 0011

	10
	0110	: 0011
-	0110
	0000

Otrzymaliśmy wynik 0010  (liczba 2). Ponieważ znaki dzielnej i dzielnika są różne, zmieniamy wartość na przeciwną: 1110 i ostatecznie otrzymujemy wynik 1110_(U2) = (-2).

Jeśli w trakcie dzielenia otrzymamy resztę, to musi ona mieć ten sam znak, co dzielna. Zbierzmy i podsumujmy  reguły określania znaków wyniku i reszty z dzielenia w poniższej tabelce. Zawiera ona stan bitów znakowych.

Reguły znaków przy dzieleniu liczb całkowitych
Dzielna	Dzielnik	Wynik	Reszta
0	0	0	0
0	1	1	0
1	0	1	1
1	1	0	1

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) jak i poniżej dolnej (niedomiar). 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.

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

W poniższej tabelce zebraliśmy reguły powstawania nadmiaru i niedomiaru przy różnych operacjach arytmetycznych na liczbach w kodzie U2. Zawiera ona stany bitów znakowych.

Źródło: mgr Jerzy Wałaszek