Kod uzupełnień do dwóch (w skrócie U2 lub ZU2) – system reprezentacji liczb całkowitych w dwójkowym systemie pozycyjnym. Jest obecnie najpopularniejszym sposobem zapisu liczb całkowitych w systemach cyfrowych. Jego popularność wynika z faktu, że operacje dodawania i odejmowania są w nim wykonywane tak samo jak dla liczb binarnych bez znaku. Z tego też powodu oszczędza się na kodach rozkazów procesora.
Nazwa kodu wzięła się ze sposobu obliczania liczb przeciwnych. Dla jednobitowej liczby wartość przeciwną obliczamy odejmując daną liczbę od 2 (uzupełniamy jej wartość do dwóch). Analogicznie, dla liczb -bitowych wartości przeciwne uzyskujemy odejmując liczbę od dwukrotnej wagi najstarszego bitu W analogiczny sposób można stworzyć np. kod uzupełnień do jedności.
Zaletą tego kodu jest również istnienie tylko jednego zera. Przedział kodowanych liczb nie jest przez to symetryczny. W U2 na bitach da się zapisać liczby z zakresu:
Dla reprezentacji 8-bitowej (jednobajtowej) są to liczby od −128 do 127. Liczba nie ma liczby przeciwnej w -bitowej reprezentacji kodu U2.
Zapis liczb
W dwójkowym systemie liczbowym najstarszy bit liczby -cyfrowej ma wagę Jedyną różnicą, jaką wprowadza tu kod U2, jest zmiana wagi tego bitu na przeciwną Wartość dziesiętną liczby U2 wyraża wzór:
Najstarszy bit koduje wartość liczby, ale jest też nazywany bitem znaku, ponieważ świadczy o znaku liczby:
- jeśli jest ustawiony (=1), to liczba jest ujemna,
- jeśli jest skasowany (=0), to liczba jest dodatnia lub równa 0.
Zwiększając obszar zajmowany przez liczbę w kodzie U2 (np. z jednego bajta na dwa), dodawany obszar wypełnia się bitem znaku.
Kod U2 może być również użyty do przechowywania liczb ułamkowych o stałej pozycji przecinka. Zapisywany jest wówczas licznik ułamka o mianowniku będącym potęgą liczby dwa ( np. 2, 4, 8,...), mianownik nie jest zapisywany. Przy mnożeniu i dzieleniu takich liczb wymagane są korekty, jeśli wynik ma mieć przecinek w tym samym miejscu.
Przykład
- 11101101U2 = 1 · −27 + 1 · 26 + 1 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = −128 + 109 = −19
Liczba przeciwna
Aby zamienić liczbę w U2 na przeciwną, należy wykonać dwa kroki:
- dokonać inwersji bitów, czyli zamienić 0 na 1 i odwrotnie;
- zwiększyć wynik o 1.
Przykład
Dana jest liczba:
- 7410 = 0 · (− (27)) + 1 · 26 + 0 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 0 · 20 = 01001010U2
dokonujemy inwersji:
- 10110101
i zwiększamy o 1:
- 10110110U2 = 1 · (-(27))+ 0 · 26 + 1 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 0 · 20 = −7410
Dodawanie i odejmowanie liczb
Dodawanie i odejmowanie w U2 odbywa się standardową metodą – traktujemy liczby jako zwykłe liczby binarne (dodatnie), dodajemy je i odejmujemy, a wynik otrzymamy w kodzie U2. Dodawanie i odejmowanie odbywa się łącznie z bitem znaku. Jeśli przeniesienie (lub pożyczka dla odejmowania) wystąpi tylko na bit znaku albo poza niego (niejednocześnie lub wcale), wówczas mamy do czynienia z nadmiarem. Oznacza to, że wynik nie mieści się w kodowanym zakresie.
Przykład
W precyzji do części czwartych, w ośmiobitowej reprezentacji, liczby są kodowane:
Dodawanie
11010001
+11100010
---------
110110011
|
Dziewiąty bit wyniku jest odrzucany przy określaniu liczby (jest on używany tylko do określenia czy nastąpił nadmiar). Tu wystąpiło przeniesienie na bit znaku i z niego, dlatego nadmiar nie wystąpił – wynik nie przekroczył zakresu i jest poprawny.
Odejmowanie
Odejmowanie jest realizowane, jak odejmowanie w naturalnym kodzie dwójkowym. Przykład z reprezentacją do części czwartych:
11010001
−11100010
---------
111101111
|
Odejmowanie może być zamienione na dodanie liczby przeciwnej, dlatego w niektórych procesorach zrealizowano tylko operację tworzenia liczby przeciwnej i dodawanie, a odejmowanie stałej wartości może nie występować.
Powyższe działanie realizowane jako wzięcie liczby przeciwnej i dodawanie
przeciwna do 11100010 = 00011110
11010001
+00011110
--------
11101111
|
Mnożenie liczb
I wariant metody Bootha
Algorytm słowny:
- Badamy kolejne pary bitów mnożnika.
- Jeżeli badana para jest kombinacją 10 to od iloczynu częściowego odejmujemy mnożną, wynik przesuwamy o jedno miejsce w prawo.
- Jeżeli jest to para 01 to dodajemy mnożną do iloczynu częściowego, przesuwamy wynik o jedno miejsce w prawo
- Jeżeli są to pary 00 lub 11 to nie wykonujemy żadnego działania, tylko przesuwamy o jedno miejsce w prawo.
- Gdy w skład pary wchodzi bit znaku to nie wykonujemy przesunięcia.
Przykład
Uwaga: część całkowita w zapisie binarnym została pominięta – zapis jest postaci bit_znaku.bity_ułamka
Analizujemy bity liczby (od prawej do lewej strony), dodajemy i odejmujemy liczbę
0.0000 (iloczyn częściowy)
−1.1011 (jest 10, odejmuje)
------
0.0101
0.00101 → (i przesuwa)
+1.1011 (jest 01, dodaje)
-------
1.11011
1.111011 → (i przesuwa)
1.1111011 → (jest 00, tylko przesuwa)
−1.1011 (jest 1.0, ale jest bit znaku, to nie przesuwa )
---------
0.0100011
|
Wynik otrzymujemy w kodzie znak-moduł (ZM).
Sprawdzenie
II wariant metody Bootha
Algorytm słowny:
- Oznaczamy i inicjujemy: A – mnożna, iloczyn częściowy = 0
- Przesuwamy mnożną o jedno miejsce w prawo (wykonujemy działanie )
- Badamy ostatni bit mnożnika:
- jeśli jest równy 1 to dodaj mnożną do iloczynu częściowego
- jeśli równy 0 to nie wykonuj żadnego działania (dodaj 0)
- Przesuwamy mnożnik o jedno miejsce w prawo, czyli przechodzimy do badania kolejnego bitu mnożnika.
- Przesuwamy iloczyn częściowy o jedno miejsce w prawo, powtarzamy 3 ostatnie punkty do momentu aż napotkamy bit znaku
- Jeśli bit znaku jest równy 1 to odejmujemy mnożną od iloczynu częściowego, jeśli jest równy 0 to nie wykonujemy żadnego działania.
- Uzyskany iloczyn częściowy przesuwamy o jedno miejsce w lewo (działanie A · 2).
Przykład
Uwaga: część całkowita w zapisie binarnym została pominięta – zapis jest postaci bit_znaku.bity_ułamka
Analizuję bity liczby B (mnożnika) od prawej do lewej strony, dodaję i odejmuję liczbę A (mnożną).
– przesuwamy mnożną o jedno miejsce w prawo
0.0000
+0.0011 (analizuję 1)
------
0.0011
0.00011 →
+0.0011 (analizuję 1)
-------
0.01001
0.001001 →
0.0001001 → (analizuję 0)
+0.0011 (analizuję 1)
---------
0.0100001
0.00100001 →
−0.0011 (analizuję 1 – bit znaku)
----------
1.11110001
1.1110001 ←
|
Wynik otrzymujemy w kodzie uzupełnień do dwóch.
Sprawdzenie
Dzielenie liczb
Metoda porównawcza
Algorytm słowny:
- Jeżeli przesunięta reszta częściowa jest większa lub równa od dzielnika, to kolejny bit ilorazu qi = 1, odejmujemy dzielnik od tej reszty.
- Jeżeli przesunięta reszta częściowa jest mniejsza od dzielnika, to kolejny bit ilorazu qi = 0.
- Dokonujemy przesunięcia otrzymanego wyniku o jedno miejsce w lewo i przechodzimy do punktu pierwszego.
Przykład
Uwaga: część całkowita w zapisie binarnym została pominięta – zapis jest postaci bity_ułamka
Uwaga 2: dzielenie odbywa się w kodzie znak-moduł z pominięciem bitu znaku (operujemy na modułach liczb), w przeciwieństwie do pozostałych metod
(dzielna)
(dzielnik)
RC = A = 0011001 (RC ≥ B, więc q1 = 1)
011001 ←
−0101
------
000101
RC = 00101 ← (RC < B, więc q2 = 0)
RC = 0101 ← (RC ≥ B, więc q3 = 1)
−0101
----
RC = 0000 (kolejna reszta częściowa = 0)
|
Otrzymany wynik, złożony z kolejnych bitów od q1 do q3 jest modułem liczby wynikowej, postaci q1q2q3.
Bit znaku (z) tej liczby określamy na podstawie bitów znaku dzielnej (a) i dzielnika (b) przy pomocy operacji logicznej XOR: z = a XOR b. Tak więc przy różnych bitach znaku daje ona wynik 1, przy takich samych daje 0.
Wynik otrzymujemy w kodzie znak-moduł i jest on równy 1.101ZM.
Sprawdzenie
Metoda nierestytucyjna
Algorytm słowny:
- Założenie: moduł dzielnej musi być mniejszy od modułu dzielnika w kodzie ZM
- Metoda polega na badaniu znaku dzielnika i kolejnej reszty częściowej (pierwsza reszta częściowa jest równa dzielnej).
- jeżeli znaki te są zgodne to odejmujemy dzielnik od przesuniętej w lewo kolejnej reszty częściowej, kolejny bit ilorazu qi = 1
- jeżeli znaki są różne to dodajemy dzielnik do przesuniętej w lewo kolejnej reszty częściowej, kolejny bit ilorazu qi = 0
- Powtarzamy poprzedni punkt aż do momentu, gdy kolejna reszta częściowa będzie równa 0
- Do otrzymanego wyniku dodajemy poprawkę równą −1 + 2−n, gdzie n jest liczbą bitów pseudoilorazu.
Przykład
Uwaga: część całkowita w zapisie binarnym została pominięta – zapis jest postaci bit_znaku.bity_ułamka
(dzielna)
(dzielnik)
1.1110001 (znaki różne, 1 oraz 0, więc q0 = 0)
1.110001 ←
+0.011
--------
0.001001 (znaki zgodne, 0 oraz 0, więc q1 = 1)
0.01001 ←
−0.011
-------
1.11101 (znaki różne, więc q2 = 0)
1.1101 ←
+0.011
------
0.0011 (znaki zgodne, więc q3 = 1)
0.011 ←
−0.011
-----
0.000 (kolejna reszta częściowa = 0)
|
Otrzymany wynik, złożony z kolejnych bitów od q0 do q3 jest pseudoilorazem (PQ), gdzie q0 jest jego bitem znakowym, a kolejne są kolejnymi bitami liczby postaci q0q1q2q3. Tak więc PQ = 0.101
Do pseudoilorazu dodajemy poprawkę
0.101 (pseudoiloraz)
+1.0001 (poprawka)
------
1.1011
|
Wynik otrzymujemy w kodzie uzupełnień do dwóch.
Sprawdzenie
Zobacz też
Linki zewnętrzne
- Symulator algorytmu Booth’a
- Standardowe Techniki Kompresji. dsp.agh.edu.pl. [zarchiwizowane z tego adresu (2013-12-04)]. (materiały dydaktyczne AGH)