Kod uzupełnień do dwóch

1

Kod uzupełnień do dwóch

Kod uzupełnień do dwóch (w skrócie U2 lub ZU2) jest obecnie najpopularniejszym sposobem zapisu liczb

całkowitych oraz ułamkowych przedstawionych w formacie stałoprzecinkowym 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

n

). 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:

Dla 8 bitów (bajta) są to liczby od –128 do 127. Liczba –2

n–1

nie posiada swojego przeciwieństwa w n-bitowej

reprezentacji kodu U2.

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 bajta na dwa), dodawany obszar wypełnia

się bitem znaku.

Kod U2 może być połączony z kodem stałopozycyjnym w celu umożliwienia zapisu liczb niecałkowitych.

Wymagana jest wtedy umowa co do miejsca położenia przecinka oddzielającego część całkowitą od ułamkowej

(może on również leżeć poza cyframi znaczącymi liczby). Liczby takie można traktować jako liczby całkowite przy

dodawaniu i odejmowaniu. Przy mnożeniu i dzieleniu wymagane są korekty, jeśli wynik ma mieć w tym samym

miejscu przecinek.

Zapis dwójkowy liczb zmiennoprzecinkowych na ogół nie używa wcale kodu U2, bądź używa go tylko dla

wykładnika.

Przykłady

11101101

U2

= 1 ⋅ -(2

7

) + 1 ⋅ 2

6

+ 1 ⋅ 2

5

+ 0 ⋅ 2

4

+ 1 ⋅ 2

3

+ 1 ⋅ 2

2

+ 0

⋅ 2

1

+ 1 ⋅ 2

0

= -19

10

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.

Kod uzupełnień do dwóch

2

Przykład

Dana jest liczba:

01001010

U2

= 0 ⋅ -(2

7

) + 1 ⋅ 2

6

+ 0 ⋅ 2

5

+ 0 ⋅ 2

4

+ 1 ⋅ 2

3

+ 0 ⋅ 2

2

+ 1

⋅ 2

1

+ 0 ⋅ 2

0

= 74

10

Dokonujemy inwersji:

10110101

Zwiększamy o 1:

10110110

U2

= 1 ⋅ -(2

7

) + 0 ⋅ 2

6

+ 1 ⋅ 2

5

+ 1 ⋅ 2

4

+ 0 ⋅ 2

3

+ 1 ⋅ 2

2

+ 1

⋅ 2

1

+ 0 ⋅ 2

0

= -74

10

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.

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.

Dodawanie

1.10100,010

+1.11000,011

------------

1.01100,101

Kod uzupełnień do dwóch

3

Odejmowanie

Odejmowanie jest realizowane, podobnie jak dodawanie

1.10100,010

-1.11000,011

------------

1.11011,111

Odejmowanie może być zamienione na dodanie liczby przeciwnej, dlatego w niektórych procesorach zrealizowano

tylko operację tworzenia liczby przeciwnej i dodawanie. Przykład odejmowania przez zamianę liczby na liczbę

przeciwną.

przeciwna do 1.11000,011 = 0.00111,101

1.10100,010

+0.00111,101

------------

1.11011,111

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

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

Kod uzupełnień do dwóch

4

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:

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

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

Kod uzupełnień do dwóch

5

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:

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

(dzielna)

(dzielnik)

RC = A = 0011001 (RC ≥ B, więc q

1

= 1)

011001 <-

-0101
------

000101

RC = 00101 <- (RC < B, więc q

2

= 0)

RC = 0101 <- (RC ≥ B, więc q

3

= 1)

-0101

----

RC = 0000 (kolejna reszta częściowa = 0)

Kod uzupełnień do dwóch

6

Otrzymany wynik, złożony z kolejnych bitów od q

1

do q

3

jest modułem liczby wynikowej, postaci q

1

q

2

q

3

.

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.

Sprawdzenie

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

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

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

0

= 0)

1.110001 <-

+0.011

--------

0.001001 (znaki zgodne, 0 oraz 0, więc q

1

= 1)

0.01001 <-

-0.011

-------

1.11101 (znaki różne, więc q

2

= 0)

1.1101 <-

+0.011

------

0.0011 (znaki zgodne, więc q

3

= 1)

0.011 <-

-0.011

-----

0.000 (kolejna reszta częściowa = 0)

Otrzymany wynik, złożony z kolejnych bitów od q

0

do q

3

jest pseudoilorazem (PQ), gdzie q

0

jest jego bitem

znakowym, a kolejne są kolejnymi bitami liczby postaci q

0

q

1

q

2

q

3

. Tak więc PQ = 0.101

Do pseudoilorazu dodajemy poprawkę

Kod uzupełnień do dwóch

7

0.101 (pseudoiloraz)

+1.0001 (poprawka)

------

1.1011

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

Sprawdzenie

Zobacz też

• Kod znak-moduł

• Kod uzupełnień do jedności

• Symulator algorytmu Booth'a

[1]

Przypisy

[1] http:/

/

www.

ecs.

umass.

edu/

ece/

koren/

arith/

simulator/

Booth/

Article Sources and Contributors

8

Article Sources and Contributors

Kod uzupełnień do dwóch  Source: http://pl.wikipedia.org/w/index.php?oldid=19419508  Contributors: Bartozza, CiaPan, Gtworek, Konradzik, Lukasz Lukomski, ManiAkF, Marniak, Mik,
Mlepicki, PDD, Roo72, Stok, Tilia, Wojciech mula, Wumarex, Zbyszekprasak, Zergu, Zerro, Zolv, 31 anonimowe edycje

Licencja

Creative Commons Attribution-Share Alike 3.0 Unported
http:/

/

creativecommons.

org/

licenses/

by-sa/

3.

0/