Dvojkový doplněk
Dvojkový doplněk (též doplňkový kód) je způsob kódování celých, tedy kladných i záporných čísel ve dvojkové soustavě používaný v počítačích. Dvojkový doplněk umožňuje zjednodušit konstrukci aritmeticko-logické jednotky uvnitř procesoru díky tomu, že sčítání a odečítání se provádí pro čísla se znaménkem stejně jako pro čísla bez znaménka, odlišná je pouze interpretace přetečení. Odečítání lze převést na sečtení prvního operandu s dvojkovým doplňkem druhého. Dvojkový doplňkový kód je nejrozšířenějším způsobem reprezentace celých čísel se znaménkem v počítači.
Výhody a nevýhody
K výhodám dvojkového doplňku patří, že neexistuje kladná a záporná nula (jako u jedničkového doplňku). Nevýhodou je naopak fakt, že zobrazený interval je nesymetrický (např. −128 až 127 v případě osmibitových čísel nebo −32768 až 32767 v případě šestnáctibitových). Takže například nelze na daném počtu bitů vyjádřit absolutní hodnotu nejzápornějšího čísla (nejzápornější číslo je ve dvojkovém doplňku invariantní vůči negaci, stejně jako nula).
Postup kódování
Při použití dvojkového doplňku se opačné číslo získá tak, že se znegují všechny bity dvojkového zápisu čísla a k výsledku se přičte jednička. Stejného výsledku lze dosáhnout odečtením jedničky následovaném negací všech bitů. Oba postupy fungují pro kladná i záporná čísla. Při aplikaci na nejmenší zobrazitelné číslo (nejzápornější zobrazitelné číslo) je výsledkem totéž číslo (mělo by se interpretovat jako přetečení).
Jiný postup
Protože dvojkový doplněk je také neznaménkové vyjádření záporného čísla na daném rozsahu, lze ho získat jako rozdíl (maxima rozsahu +1) a absolutní hodnoty záporného čísla. Např. pro rozsah 8 bitů, kde maximum je 255, dojde při překročení rozsahu k přetečení, takže číslo 256 = 0. Potom bude znaménkovému vyjádření "-x = 0 - |x|" odpovídat neznaménkový zápis "-x = 256 - |x|".
Sčítání dvou čísel v doplňkovém kódu
Sčítání dvou kladných čísel; výsledek je kladný:
binárně bez znaménka se znaménkem
0001 1110 30 30
+ 0011 0010 + 50 + 50
=========== ===== =====
CF=0 0101 0000 80 80
PF=0 (OK) (OK)
Sčítání dvou kladných čísel; výsledek je záporný (přetečení):
binárně bez znaménka se znaménkem
0100 1011 75 75
+ 0110 0100 + 100 + 100
=========== ===== =====
CF=0 1010 1111 175 -81
PF=1 (OK) (chyba)
Sčítání záporného a kladného čísla; výsledek je záporný (přetečení při sčítání bez znamének):
binárně bez znaménka se znaménkem
1110 1100 236 -20
+ 0010 1101 + 45 + 45
=========== ===== =====
CF=1 0001 1001 25 25
PF=0 (chyba) (OK)
Sčítání záporného a kladného čísla; výsledek je záporný:
binárně bez znaménka se znaménkem
1111 0010 242 -14
+ 0000 1010 + 10 + 10
=========== ===== =====
CF=0 1111 1100 252 -4
PF=0 (OK) (OK)
Sčítání dvou záporných čísel (u čísel bez znamének dojde k přetečení):
binárně bez znaménka se znaménkem
1110 0100 228 -28
+ 1110 0111 + 231 + -25
=========== ===== =====
CF=1 1100 1011 203 -53
PF=0 (chyba) (OK)
Sčítání dvou záporných čísel (k přetečení dojde u čísel bez znamének i se znaménky):
binárně bez znaménka se znaménkem
1100 0101 197 -59
+ 1001 1011 + 155 + -101
=========== ===== =====
CF=1 0110 0000 96 -160
PF=1 (chyba) (chyba)
Je patrné, že při použití dvojkového doplňku se pro sčítání a odečítání čísel se znaménkem používají stejné operace jako pro čísla bez znaménka. Rozdíl je pouze v interpretaci čísel a ve způsobu vyhodnocování překročení číselného rozsahu: zatímco při operacích s čísly bez znaménka indikuje překročení povoleného rozsahu příznak přenosu (CF-přenos z nejvyššího bitu), při operacích se znaménkem indikuje překročení rozsahu příznak přetečení(PF- přenosy z a do nejvyššího bitu).
Výpočet rozdílu dvou čísel pomocí dvojkového doplňku
Řekněme, že máme dvě celá čísla v absolutní hodnotě 1000 0001 a 11 0110, a chceme druhé číslo odečíst od prvního.
- Zarovnáme počet bitů obou čísel – 1000 0001 a 0011 0110 (doplnění nul)
- Provedeme negaci menšitele (číslo, které je odečítáno) − 0011 0110 ⇒ 1100 1001
- Provedeme inkrementaci (přičtení jedničky) menšitele − 1100 1001 + 1 = 1100 1010
Dvojkový doplněk je tedy 1100 1010. Výpočet rozdílu provedeme sečtením menšence 1000 0001 a doplňku 1100 1010. Výsledkem tohoto součtu je číslo 10100 1011, kde ale musíme vynechat přenos jedničky do nejvyššího řádu. Konečným výsledkem je tedy číslo 0100 1011.
Ukázka 4bitového dvojkového doplňkového kódu
Následující příklad předvádí kódování čísel −8 až +7 (v desítkové soustavě) do čtyřbitového čísla ve dvojkové soustavě použitím dvojkového doplňku.
| Dvojkový doplněk | Desítkově |
|---|---|
| 0111 | 7 |
| 0110 | 6 |
| 0101 | 5 |
| 0100 | 4 |
| 0011 | 3 |
| 0010 | 2 |
| 0001 | 1 |
| 0000 | 0 |
| 1111 | −1 |
| 1110 | −2 |
| 1101 | −3 |
| 1100 | −4 |
| 1011 | −5 |
| 1010 | −6 |
| 1001 | −7 |
| 1000 | −8 |
Z příkladu ilustruje vlastnosti čísel kódovaných v DDK, o kterých pojednává další odstavec.
Vlastnosti dvojkového doplňkového kódu
- Označme indexy bitů 0, 1, 2, …, N-1, kde N je počet bitů čísla, nejvyšší bit má tedy index N-1
- Uvažujme binární součet s přetečením, který používá drtivá většina počítačů
Pak platí:
- Když je nejvyšší bit (MSB) 1, tak je číslo záporné.
- bity 0, 1, 2, …, N-2 mají váhu 20, 21, …, 2N-2
- bit N-1 (tj. MSB) má váhu -(2N-1); tato vlastnost je užitečná např. při násobení
- Při kódování do N bitů je možné zakódovat čísla od do . V uvedeném příkladě je N=4, kódovaný rozsah je od −8 do 7.
- Výsledkem binárního součtu kladného a záporného čísla ve dvojkovém doplňku je opět číslo ve dvojkovém doplňku. Například (−6 + 3)10 = (1010 + 0011)2 = 11012 = −310.
- Kladná čísla (tj. 0 až 2N-1 – 1) mají stejné kódy jako N-bitová čísla bez znaménka
- Výsledek sčítání nezávisí na pořadí sčítanců (i při přetečení)
Odkazy
Související články
- Číselná soustava
- Šestnáctková soustava
- Osmičková soustava
- Dvojková soustava
- Grayův kód
- Brownův kód
- BCD
- Binární soubor
- Kapitola Doplňkový kód v článku Dvojková soustava
Externí odkazy
Výukový kurs Číselné soustavy/Dvojková soustava ve Wikiverzitě
