Dodatečný kód

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 31. ledna 2021; kontroly vyžadují 22 úprav .

Dvojkový doplněk ( někdy „ dvojkový doplněk“ ) je nejběžnějším způsobem reprezentace záporných celých čísel v počítačích . Umožňuje nahradit operaci odčítání operací sčítání a učinit operace sčítání a odčítání stejné pro čísla se znaménkem i bez znaménka , což zjednodušuje architekturu počítače . V anglické literatuře se „ reverzní kód “ nazývá „ doplněk jedniček“ a „další kód“ se nazývá „ dvojkový doplněk“ .

Dodatečný kód pro záporné číslo lze získat invertováním jeho binárního modulu a přidáním jedničky k inverzi nebo odečtením čísla od nuly.
Kód doplňku dvojky je definován jako hodnota získaná odečtením čísla od největší mocniny dvou (z 2 N pro doplněk N-bitové sekundy).

Reprezentace záporného čísla dvojkovým doplňkem

Při zápisu čísla do doplňkového kódu je nejvýznamnější bit znaménko. Pokud je hodnota nejvýznamnějšího bitu 0, znamená to, že zbývající bity obsahují kladné binární číslo , které odpovídá přímému kódu .

Osmibitové binární číslo se znaménkem dvojky může představovat jakékoli celé číslo mezi -128 a +127 . Pokud je nejvýznamnější bit nula, pak největší celé číslo, které lze zapsat do zbývajících 7 bitů, je . $2^{7}-1=127$

Příklady:

Desetinná reprezentace	Binární reprezentace (8 bitů), kód:
Desetinná reprezentace	rovný	zadní	další
127	0111 1111	0111 1111	0111 1111
jeden	0000 0001	0000 0001	0000 0001
0	0000 0000	0000 0000	0000 0000
-0	1000 0000	1111 1111	0000 0000
-jeden	1000 0001	1111 1110	1111 1111
-2	1000 0010	1111 1101	1111 1110
-3	1000 0011	1111 1100	1111 1101
-čtyři	1000 0100	1111 1011	1111 1100
-5	1000 0101	1111 1010	1111 1011
-6	1000 0110	1111 1001	1111 1010
-7	1000 0111	1111 1000	1111 1001
-osm	1000 1000	1111 0111	1111 1000
-9	1000 1001	1111 0110	1111 0111
-deset	1000 1010	1111 0101	1111 0110
-jedenáct	1000 1011	1111 0100	1111 0101
-127	1111 1111	1000 0000	1000 0001
-128	---	---	1000 0000

Dodatečný kód v jiné číselné soustavě

Stejný princip může být také použit v počítačové reprezentaci jakékoli číselné soustavy , například pro desetinná čísla .

Transformace na příkladu desítkové číselné soustavy [1]

Kladné číslo

Hodnota aktuálních číslic čísla se nezmění, ale přidá se znaménko nejvýznamnější číslice, jejíž hodnota je 0. Například číslo [+12'345] bude mít následující zobrazení - [012'345 ]

Záporné číslo

Přidáme znaménko vyšší číslice rovnající se největší číslici této číselné soustavy , v našem případě je to 9, a také změníme zbývající číslice podle určitého pravidla; nechť je hodnota číslice každé číslice reprezentována proměnnou x , kromě znaménka jedna, pak si představte následující algoritmus akcí:

Přiřaďte proměnné x novou hodnotu rovnou výrazu 9 - x (proces získání zpětného kódu) - např. záporné číslo [ -12345 ] v přímém kódu od nejvýznamnější po nejméně významnou číslici bude vypadat takto [9' 12345 ], kde 9 je znaková číslice, a obrácená reprezentace kódu bude vypadat takto - [9'87654].
K výslednému číslu přidáme 1, takže číslo [9'87654] (první sčítání) bude vypadat jako [987'655] (dodatečný kód).
Pokud vznikla bitová přenosová situace, v jejímž důsledku vznikl nový bit, pak jej vynecháme (nejvyšší bit) a výsledné číslo považujeme za kladné. Výsledné kladné číslo bude rovnoměrně zastoupeno jak v přímém, tak v dvojkovém kódu doplňku. Máme-li například schopnost reprezentovat zápornou a kladnou nulu v této podobě, analyzujme jejich překlad do dodatečného kódu (1 znak a 4 další číslice):
- [+0] v přímém kódu [0'0000]. První a druhý doplněk jsou [0'0000].
- [-0] v přímém kódu [9'0000]. První přírůstek je [9'9999]. Při příjmu druhého doplňku se vynechá horní bit čísla [(1)0'0000] a získá se výsledná hodnota [0'0000] jako u čísla [+0].

Myšlenka reprezentace desetinného (stejně jako jakéhokoli jiného) čísla ve dvojkovém doplňkovém kódu je identická s pravidly pro binární číselný systém a může být použita v hypotetickém procesoru:

Obvyklé výkon	Rovný kód	První přidání	Druhý přidání
...	...	...	...
+13	0'0013	0'0013	0'0013
+12	0'0012	0'0012	0'0012
+11	0'0011	0'0011	0'0011
+10	0'0010	0'0010	0'0010
+9	0'0009	0'0009	0'0009
+8	0'0008	0'0008	0'0008
...	...	...	...
+2	0'0002	0'0002	0'0002
+1	0'0001	0'0001	0'0001
+0	0,0000	0,0000	0,0000
-0	9 0000	9,9999	0,0000
-jeden	9'0001	9'9998	9,9999
-2	9'0002	9'9997	9'9998
-3	9'0003	9'9996	9'9997
-čtyři	9'0004	9'9995	9'9996
...	...	...	...
-9	9'0009	9,9990	9'9991
-deset	9'0010	9'9989	9,9990
-jedenáct	9'0011	9'9988	9'9989
-12	9'0012	9'9987	9'9988
-13	9'0013	9'9986	9'9987

Aritmetika dvojkového doplňku

Sčítání a odčítání

Obě čísla jsou reprezentována dvojkovým doplňkem. Doplňkový kód obou čísel má stejný počet číslic. V tomto znázornění se čísla sčítají.

Znaky jsou různé: Pokud se v procesu sčítání vytvoří číslice, která přesahuje počáteční čísla, pak se vynechá. Výsledná hodnota je považována za kladnou , pokud jsou přímý a dvojkový doplňkový kód identické. V opačném případě negativní ve formě dodatečného kódu .

Například:

[1234] + [-78] → [0'1234] + [9'9922] = [(1)0'1156] = [1156].
[-1234] + [78] → [9'8766] + [0'0078] = [9'8844] = [-1156].

Znaky jsou stejné:

kladná čísla. Výboj neklesá, výsledek je pozitivní.
Záporná čísla. Číslice je vynechána, výsledek je záporný v kódu doplňku dvojky.

Například:

[1234] + [78] → [0'1234] + [0'0078] = [0'1312] = [1312].
[-1234] + [-78] → [9'8766] + [9'9922] = [(1)9'8688] → (první doplněk) [0'1311] → (druhý doplněk nebo pravidelná reprezentace) [0 '1312]. Při převodu z doplňku dvojky do normální reprezentace je výsledná hodnota absolutní.

Převod na dvojkový doplněk

Převod čísla z přímého kódu na další se provádí podle následujícího algoritmu.

Pokud je nejvýznamnější (znaménkový) bit čísla zapsaného v přímém kódu 0, pak je číslo kladné a neprovádějí se žádné transformace;
Pokud je nejvýznamnější (znaménková) číslice čísla zapsaného v přímém kódu 1, pak je číslo záporné, všechny číslice čísla kromě znaménka jsou převráceny a k výsledku se přičte 1.

Příklad. Převedeme záporné číslo −5 zapsané v přímém kódu na doplňkový kód. Přímý kód pro záporné číslo -5:

1000 0101

Invertujeme všechny číslice čísla kromě znaménka, čímž získáme inverzní kód (první sčítání) záporného čísla -5:

1111 1010

Přidejme k výsledku 1, čímž získáme další kód (druhý doplněk) záporného čísla -5:

1111 1011

Podobný algoritmus se používá k převodu záporného čísla -5 zapsaného v kódu doplňku dvojky na kladné číslo 5 zapsaného v přímém kódu. A to:

1111 1011

Invertujeme všechny číslice záporného čísla -5, čímž získáme kladné číslo 4 v přímém kódu:

0000 0100

Přidáním 1 k výsledku dostaneme kladné číslo 5 v přímém kódu:

0101

A zkontrolujte přidáním dalšího kódu

0000 0101 + 1111 1011 = 0000 0000, pátá a vyšší číslice se vyřadí.

p-adická čísla

V systému p -adických čísel se změna znaménka čísla provádí převodem čísla na jeho doplňkový kód. Pokud je například číselná soustava 5, pak opak 0001 5 (1 10 ) je 4444 5 (−1 10 ).

Implementace algoritmu konverze dvou komplementů (pro 8bitová čísla)

Pascal

if ( a < 0 ) then a := ( ( ne a ) nebo 128 ) + 1 ;

C/C++

int převést ( int a ) { jestliže ( a < 0 ) a = ~ ( -a ) + 1 ; _ vrátit a ; }

Výhody a nevýhody

Výhody

Obecné (procesorové) instrukce pro sčítání, odčítání a posun doleva pro čísla se znaménkem a bez znaménka (rozdíly pouze v aritmetických příznacích, které je třeba zkontrolovat pro kontrolu přetečení ve výsledku).
Absence čísla " mínus nula ".

Nevýhody

Znázornění záporného čísla není vizuálně čteno podle obvyklých pravidel, jeho vnímání vyžaduje zvláštní zručnost nebo dodatečné výpočty, aby se dostal do normální podoby.
V některých reprezentacích (jako je BCD ) nebo jejich dílčích částech (jako je mantisa čísla s plovoucí desetinnou čárkou ) je dodatečné kódování nepohodlné.
Modul největšího čísla se nerovná modulu nejmenšího čísla. Například pro osmibitové celé číslo se znaménkem je maximální číslo 127 10 = 01111111 2 , minimální číslo je -128 10 = 10000000 2 . V souladu s tím neexistuje pro žádné číslo opak. Operace změny znaménka může vyžadovat dodatečné ověření.

Příklad programové konverze

Pokud čtete data ze souboru nebo oblasti paměti, kde jsou uložena ve dvou doplňcích (například soubor WAVE), může být nutné převést bajty. Pokud jsou data uložena v 8 bitech, hodnoty 128-255 musí být záporné.

C# .NET / C styl

byte b1 = 254 ; //11111110 (binarni) byte b2 = 121 ; //01111001 (binarni) byte c = 1 <<( sizeof ( byte )* 8 - 1 ); //2 je umocněno na 7. Výsledek: 10000000 (binární) byte b1Conversion =( c ^ b1 ) - c ; //Výsledek: -2. A ve skutečnosti binární dvojkový doplňkový kód. byte b2Conversion =( c ^ b2 ) - c ; //Výsledek zůstane 121, protože znaménkový bit je nula.

Rozšíření znaménka

Rozšíření znaménka (angl. Sign extension ) - operace s binárním číslem, která umožňuje zvýšit počet bitů při zachování znaménka a hodnoty. Provádí se sčítáním číslic od nejvýznamnější číslice. Pokud je číslo kladné (nejvýznamnější číslice je 0), přičtou se nuly, pokud je záporné (nejvýznamnější číslice je 1), přidají se jedničky.

Příklad

Desetinné číslo	binární číslo (8 číslic)	binární číslo (16 číslic)
deset	0000 1010	0000 0000 0000 1010
−15	1111 0001	1111 1111 1111 0001

Viz také

Obrácený kód
Přímý kód
celočíselný typ
Boothův algoritmus je specializovaný násobící algoritmus pro čísla dvojkového doplňku

Literatura

Behrooz Parhami. 2.3. Zastoupení doplňku, 2.4. Čísla s doplňkem dvojky a jedničky // Počítačová aritmetika: Algoritmy a návrhy hardwaru . - New York: Oxford University Press, 2000. - S. 22-27. — 510p. — ISBN 0-19-512583-5 .
Samofalov K.G., Romankevich A.M., Valuysky V.N., Kanevsky Yu.S., Pinevich M.M. Aplikovaná teorie číslicových automatů. - K . : Vishcha school, 1987. - 375 s.

Odkazy

↑ Florida Tech . Získáno 28. listopadu 2020. Archivováno z originálu dne 8. října 2016. (neurčitý)