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:

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]

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:

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]

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

Liczba przeciwna[edytuj]

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]

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]

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

W precyzji do części czwartych, w ośmiobitowej reprezentacji, liczby są kodowane:

Dodawanie[edytuj]

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

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

I wariant metody Bootha[edytuj]

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]

Uwaga: część całkowita w zapisie binarnym została pominięta – zapis jest postaci bit_znaku.bity_ułamka

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]

II wariant metody Bootha[edytuj]

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

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

Dzielenie liczb[edytuj]

Metoda porównawcza[edytuj]

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]

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

Metoda nierestytucyjna[edytuj]

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 reszta 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]

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

Zobacz też[edytuj]

Linki zewnętrzne[edytuj]