Kod uzupełnień do dwóch

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Kod uzupełnień do dwóch (w skrócie U2 lub ZU2) jest obecnie najpopularniejszym sposobem zapisu liczb całkowitych na bitach. 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^n–1 = 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 będzie zatem symetryczny. W U2 na n bitach da się zapisać liczby z zakresu:

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

Dla 8 bitów (bajtu) są to liczby od –128 do 127. Liczba –2^n–1 nie posiada swojego przeciwieństwa w n-bitowej reprezentacji kodu U2.

[edytuj] Zapis liczb

W dwójkowym systemie liczbowym najstarszy bit liczby n-cyfrowej ma wagę 2^n–1. Jedyną różnicą, jaką wprowadza tu kod U2, jest zmiana wagi tego bitu na przeciwną (–2^n–1). Bit ten jest nazywany bitem znaku, ponieważ świadczy o znaku całej liczby – jeśli jest ustawiony (=1) cała liczba jest ujemna, jeśli jest skasowany (=0) – liczba jest dodatnia lub równa 0.

Zwiększając obszar zajmowany przez liczbę w kodzie U2 (np. z jednego bajtu na dwa), dodawany obszar wypełnia się bitem znaku.

System może też być użyty do kodowania liczb rzeczywistych wówczas używa się systemu liczb stałoprzecinowych, bo wymagana jest wtedy umowa co do miejsca położenia przecinka oddzielajacego część całkowitą od ułamkowej. Przyjmuje się, że określona liczba bitów z prawej strony oznacza część ułamkową. Liczby takie można też traktować jako liczby całkowite.

Przykład:

$6 \frac 3 4$ z dokładnością do 3 bitów po przecinku odpowiada liczbie 110,110, bo $6 \frac 3 4 * 2^3 = 54 = 110110$ .

Zapis dwójkowy liczb zmiennoprzecinkowych na ogół nie używa wcale kodu U2, bądź używa go tylko do zapisu wykładnika.

[edytuj] Przykłady

11101101_U2 = 1 ⋅ -(2⁷) + 1 ⋅ 2⁶ + 1 ⋅ 2⁵ + 0 ⋅ 2⁴ + 1 ⋅ 2³ + 1 ⋅ 2² + 0 ⋅ 2¹ + 1 ⋅ 2⁰ = -19₁₀

[edytuj] Liczba przeciwna

Aby zamienić liczbę w U2 na przeciwną, należy wykonać dwa kroki:

dokonać inwersji bitów, czyli pozamieniać 0 na 1 i odwrotnie;
zwiększyć wynik o 1.

Można też posłużyć się metodą podaną na wstępie, ale powyższa metoda jest prostsza i działa również na procesorach, które nie mają operacji odejmowania.

[edytuj] Przykład

Dana jest liczba:

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

Dokonujemy inwersji:

10110101

Zwiększamy o 1:

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

[edytuj] Dodawanie i odejmowanie liczb

Dodawanie i odejmowanie w U2 odbywa się standardową metodą – traktujemy liczby jako zwykłe liczby binarne (dodatnie), dodajemy je lub odejmujemy, a wynik otrzymujemy w zapisie U2. Dodawanie i odejmowanie odbywa się łącznie z bitem znaku, a przeniesienia i pożyczki poza najstarszy bit (bit znaku) ignorujemy. Jeśli jednak przepełnienie (lub pożyczka) nie będzie występować jednocześnie na bit znaku i poza niego, wówczas możemy być pewni przekroczenia zakresu wyniku.

[edytuj] Przykład

Uwaga: przecinek oznacza odddzielenie części całkowitej od ułamkowej, kropka znaku liczby od wartości w U2

Rezerwujemy odpowiednią ilość "bitów" uzupełniając z lewej strony bitem znaku, a z prawej zerami zgodnie z zasadą zapisu w U2.

$-11\frac{3}{4} = 1.0100,01_\operatorname{U2}$

$-7\frac{5}{8} = 1.000,011_\operatorname{U2}$

[edytuj] Dodawanie

$-11\frac{3}{4} + -7\frac{5}{8} = -19\frac{3}{8}$

 1.10100,010
+1.11000,011
------------
 1.01100,101

$1.01100,101_\operatorname{U2} = -19\frac{3}{8}$

[edytuj] Odejmowanie

$-11\frac{3}{4} - -7\frac{5}{8} = -4\frac{1}{8}$

 1.10100,010
-1.11000,011
------------
 1.11011,111

$1.11011,111_\operatorname{U2} = -4\frac{1}{8}$

[edytuj] Mnożenie liczb

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

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

[edytuj] Sprawdzenie

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

[edytuj] 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 $\frac{A}{2}$ )
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)
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).

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

[edytuj] Sprawdzenie

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

[edytuj] Dzielenie liczb

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

[edytuj] 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 q₁ = 1)
         011001   <-
        -0101
         ------
         000101
    RC = 00101    <- (RC < B, więc q₂ = 0)
    RC = 0101     <- (RC ≥ B, więc q₃ = 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.

[edytuj] Sprawdzenie

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

[edytuj] Metoda nierestytucyjna

Algorytm słowny:

Założenie: moduł dzielnej musi być mniejszy od modułu dzielnika (|A| < |B|) w kodzie ZM
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ęśiowej, 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
Powtarzamy poprzedni punkt aż do momentu, gdy kolejna resta częściowa będzie równa 0
Do otrzymanego wyniku dodajemy poprawkę równą -1 + 2^-n, gdzie n jest liczbą bitów pseudoilorazu.

[edytuj] 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 q₀ = 0)
   1.110001   <-
  +0.011
   --------
   0.001001      (znaki zgodne, 0 oraz 0, więc q₁ = 1)
   0.01001    <-
  -0.011
   -------
   1.11101       (znaki różne, więc q₂ = 0)
   1.1101     <-
  +0.011
   ------
   0.0011        (znaki zgodne, więc q₃ = 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.

[edytuj] Sprawdzenie

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

[edytuj] Zobacz też

Źródło: "http://pl.wikipedia.org../../../k/o/d/Kod_uzupe%C5%82nie%C5%84_do_dw%C3%B3ch.html"

Kategoria: Komputerowe reprezentacje danych

Kod uzupełnień do dwóch

Z Wikipedii

Spis treści

[edytuj] Zapis liczb

[edytuj] Przykłady

[edytuj] Liczba przeciwna

[edytuj] Przykład

[edytuj] Dodawanie i odejmowanie liczb

[edytuj] Przykład

[edytuj] Dodawanie

[edytuj] Odejmowanie

[edytuj] Mnożenie liczb

[edytuj] I wariant metody Bootha

[edytuj] Przykład

[edytuj] Sprawdzenie

[edytuj] II wariant metody Bootha

[edytuj] Przykład

[edytuj] Sprawdzenie

[edytuj] Dzielenie liczb

[edytuj] Metoda porównawcza

[edytuj] Przykład

[edytuj] Sprawdzenie

[edytuj] Metoda nierestytucyjna

[edytuj] Przykład

[edytuj] Sprawdzenie

[edytuj] Zobacz też

Views

nawigacja

techniczne

zmiany

Szukaj

W innych językach