Kod uzupełnień do dwóch

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 n-bitowych wartości przeciwne uzyskujemy odejmując liczbę od dwukrotnej wagi najstarszego bitu (2·2ⁿ⁻¹ = 2ⁿ). 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 n bitach da się zapisać liczby z zakresu:

$[- 2^{n-1}\quad ,\quad 2^{n-1}-1]$

Dla reprezentacji 8-bitowej (jednobajtowej) są to liczby od −128 do 127. Liczba −2ⁿ⁻¹ nie ma liczby przeciwnej w n-bitowej reprezentacji kodu U2.

Zapis liczb

W dwójkowym systemie liczbowym najstarszy bit liczby n-cyfrowej ma wagę 2ⁿ⁻¹. Jedyną różnicą, jaką wprowadza tu kod U2, jest zmiana wagi tego bitu na przeciwną (-1 * (2ⁿ⁻¹)). Wartość dziesiętną liczby U2 wyraża wzór:

$-a_{n-1}\times 2^{n-1} + \sum_{i=0}^{n-2} a_i\times 2^i$

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 (2ⁿ, 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

11101101_U2 = 1 · (−2⁷) + 1 · 2⁶ + 1 · 2⁵ + 0 · 2⁴ + 1 · 2³ + 1 · 2² + 0 · 2¹ + 1 · 2⁰ = −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:

74₁₀ = 0 · (−2⁷) + 1 · 2⁶ + 0 · 2⁵ + 0 · 2⁴ + 1 · 2³ + 0 · 2² + 1 · 2¹ + 0 · 2⁰ = 01001010_U2

dokonujemy inwersji:

10110101

i zwiększamy o 1:

10110110_U2 = 1 · (−2⁷) + 0 · 2⁶ + 1 · 2⁵ + 1 · 2⁴ + 0 · 2³ + 1 · 2² + 1 · 2¹ + 0 · 2⁰ = −74₁₀

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 (nie jednocześnie lub wcale), wówczas mamy do czynienia z przepełnieniem. 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:

$-11\frac{3}{4} = \frac {-47} 4 \leftrightarrow -(00101111_\operatorname{U2}) = 11010001_\operatorname{U2}$

$-7\frac{2}{4} = \frac {-30} 4 \leftrightarrow -(00011110_\operatorname{U2}) = 11100010_\operatorname{U2}$

Dodawanie

$-11\frac{3}{4} + -7\frac{2}{4} = -19\frac{1}{4} = \frac {-77} 4 \leftrightarrow 10110011_{\operatorname U2}$

11010001 +11100010 ------------ 110110011 = 10110011

Dziewiąty bit wyniku jest odrzucany przy określaniu liczby (jest on używany tylko do określenia czy nastąpiło przepełnienie). Tu wystąpiło przeniesienie na bit znaku i z niego, dlatego przepełnienie nie wystąpiło – 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:

$-11\frac{3}{4} - (-7\frac{2}{4}) = \frac {-47} 4 - \frac {-30} 4 \leftrightarrow 11010001_\operatorname{U2} - 11100010_\operatorname{U2} = 11101111_\operatorname{U2} = \frac {-17} 4$

11010001 −11100010 ------------ 111101111 = 11101111

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

$-11\frac{3}{4} - (-7\frac{2}{4}) = \frac {-47} 4 - \frac {-30} 4 \leftrightarrow$

$\leftrightarrow 11010001_\operatorname{U2} - 11100010_\operatorname{U2} = 11010001_\operatorname{U2} + 00011110_\operatorname{U2} = 11101111_\operatorname{U2}$

przeciwna do 11100010 = 00011110 11010001 +00011110 ------------ 11101111

Mnożenie liczb

I wariant metody Bootha

Algorytm słowny:

1. Badamy kolejne pary bitów mnożnika.
2. Jeżeli badana para jest kombinacją 10 to od iloczynu częściowego odejmujemy mnożną, wynik przesuwamy o jedno miejsce w prawo.
3. Jeżeli jest to para 01 to dodajemy mnożną do iloczynu częściowego, przesuwamy wynik o jedno miejsce w prawo
4. Jeżeli są to pary 00 lub 11 to nie wykonujemy żadnego działania, tylko przesuwamy o jedno miejsce w prawo.
5. 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

$A = -\frac{5}{16} = 1.1011_\operatorname{U2}$

$B = -\frac{7}{8} = -\frac{14}{16} = 1.0010_\operatorname{U2}$

Analizuję bity liczby B (od prawej do lewej strony), dodaję i odejmuję liczbę A.

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

$0.0100011_\operatorname{ZM} = \frac{35}{128} = -\frac{5}{16} \cdot -\frac{7}{8}$

II wariant metody Bootha

Algorytm słowny:

1. Oznaczamy i inicjujemy: A – mnożna, iloczyn częściowy = 0
2. Przesuwamy mnożną o jedno miejsce w prawo (wykonujemy działanie $\frac{A}{2}$)
3. Badamy ostatni bit mnożnika:
   1. jeśli jest równy 1 to dodaj mnożną do iloczynu częściowego
   2. jeśli równy 0 to nie wykonuj żadnego działania (dodaj 0)
4. Przesuwamy mnożnik o jedno miejsce w prawo, czyli przechodzimy do badania kolejnego bitu mnożnika.
5. Przesuwamy iloczyn częściowy o jedno miejsce w prawo, powtarzamy 3 ostatnie punkty do momentu aż napotkamy bit znaku
6. 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.
7. 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

$A = \frac{3}{8} = 0.011_\operatorname{U2}$

$B = -\frac{5}{16} = 1.1011_\operatorname{U2}$

Analizuję bity liczby B (mnożnika) od prawej do lewej strony, dodaję i odejmuję liczbę A (mnożną).

$A = \frac{A}{2} = 0.0011_\operatorname{U2}$ – 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

$1.1110001_\operatorname{U2} = 1.0001111_\operatorname{ZM} = -\frac{15}{128} = \frac{3}{8} \cdot -\frac{5}{16}$

Dzielenie liczb

Metoda porównawcza

Algorytm słowny:

1. Jeżeli przesunięta reszta częściowa jest większa lub równa od dzielnika, to kolejny bit ilorazu q_i = 1, odejmujemy dzielnik od tej reszty.
2. Jeżeli przesunięta reszta częściowa jest mniejsza od dzielnika, to kolejny bit ilorazu q_i = 0.
3. 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

$A = -\frac{25}{128} = 1.0011001_\operatorname{ZM}$ (dzielna)

$B = \frac{5}{16} = 0.0101_\operatorname{ZM}$ (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 q₁ do q₃ jest modułem liczby wynikowej, postaci q₁q₂q₃.

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.101_ZM.

Sprawdzenie

$1.101_\operatorname{ZM} = -\frac{5}{8} = \frac{-\frac{25}{128}}{\frac{5}{16}}$

Metoda nierestytucyjna

Algorytm słowny:

1. Założenie: moduł dzielnej musi być mniejszy od modułu dzielnika (|A| < |B|) w kodzie ZM
2. Metoda polega na badaniu znaku dzielnika i kolejnej reszty częściowej (pierwsza reszta częściowa jest równa dzielnej).
   1. jeżeli znaki te są zgodne to odejmujemy dzielnik od przesuniętej w lewo kolejnej reszty częściowej, kolejny bit ilorazu q_i = 1
   2. jeżeli znaki są różne to dodajemy dzielnik do przesuniętej w lewo kolejnej reszty częściowej, kolejny bit ilorazu q_i = 0
3. Powtarzamy poprzedni punkt aż do momentu, gdy kolejna resta częściowa będzie równa 0
4. Do otrzymanego wyniku dodajemy poprawkę równą −1 + 2⁻ⁿ, 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

$A = -\frac{15}{128} = 1.1110001_\operatorname{U2}$ (dzielna)

$B = \frac{3}{8} = 0.011_\operatorname{U2}$ (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 q₀ do q₃ jest pseudoilorazem (PQ), gdzie q₀ jest jego bitem znakowym, a kolejne są kolejnymi bitami liczby postaci q₀q₁q₂q₃. Tak więc PQ = 0.101

Do pseudoilorazu dodajemy poprawkę

$P = -1 + 2^{-4} = -\frac{15}{16} = 1.0001_\operatorname{U2}$

0.101 (pseudoiloraz) +1.0001 (poprawka) ------ 1.1011

Wynik otrzymujemy w kodzie uzupełnień do dwóch.

Sprawdzenie

$1.1011_\operatorname{U2} = 1.0101_\operatorname{ZM} = -\frac{5}{16} = \frac{-\frac{15}{128}}{\frac{3}{8}}$

Zobacz też

• Kod znak-moduł
• Kod uzupełnień do jedności
• Symulator algorytmu Booth'a