Kod uzupełnień do dwóch

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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·2n−1 = 2n). 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 −2n−1 nie ma liczby przeciwnej w n-bitowej reprezentacji kodu U2.

Zapis liczb[edytuj | edytuj kod]

W dwójkowym systemie liczbowym najstarszy bit liczby n-cyfrowej ma wagę 2n−1. Jedyną różnicą, jaką wprowadza tu kod U2, jest zmiana wagi tego bitu na przeciwną (-1 * (2n−1)). 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 (2n, 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[edytuj | edytuj kod]

11101101U2 = -1 · (27) + 1 · 26 + 1 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = −128 + 109 = −19

Liczba przeciwna[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Dana jest liczba:

7410 = 0 · (-1) · (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 · (-1) · (27) + 0 · 26 + 1 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 0 · 20 = −7410

Dodawanie i odejmowanie liczb[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

 11010001
+11100010
 --------
110110011

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[edytuj | edytuj kod]

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

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[edytuj | edytuj kod]

I wariant metody Bootha[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

II wariant metody Bootha[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

Dzielenie liczb[edytuj | edytuj kod]

Metoda porównawcza[edytuj | edytuj kod]

Algorytm słowny:

  1. 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.
  2. Jeżeli przesunięta reszta częściowa jest mniejsza od dzielnika, to kolejny bit ilorazu qi = 0.
  3. Dokonujemy przesunięcia otrzymanego wyniku o jedno miejsce w lewo i przechodzimy do punktu pierwszego.

Przykład[edytuj | edytuj kod]

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 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[edytuj | edytuj kod]

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

Metoda nierestytucyjna[edytuj | edytuj kod]

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 qi = 1
    2. jeżeli znaki są różne to dodajemy dzielnik do przesuniętej w lewo kolejnej reszty częściowej, kolejny bit ilorazu qi = 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 + 2n, gdzie n jest liczbą bitów pseudoilorazu.

Przykład[edytuj | edytuj kod]

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

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[edytuj | edytuj kod]

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

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]