Reprezentace podepsaných čísel - Signed number representations

V práci na počítači , podepsané číslo reprezentace jsou zapotřebí ke kódování záporných čísel v binární číslo systémech.

V matematice jsou záporná čísla v jakékoli základně reprezentována jejich předponou znaménkem minus („ -“). V počítačovém hardwaru jsou však čísla reprezentována pouze jako sekvence bitů , bez dalších symbolů. Čtyři Nejznámějšími způsoby rozšíření binární číselnou soustavu reprezentovat podepsané čísla jsou: sign-and-velikost , jedničkový doplněk , dvě části , a kompenzovat binární . Některé z alternativních metod používají místo explicitní znaky implicitní znaky, například záporné binární, pomocí báze −2 . Odpovídající metody lze vymyslet pro jiné základy , ať už kladné, záporné, zlomkové nebo jiné zpracování takových témat.

Neexistuje žádné definitivní kritérium, podle kterého by některá z reprezentací byla univerzálně lepší. U celých čísel je zastoupení používané ve většině současných výpočetních zařízení doplňkem dvou, ačkoli mainframy řady Unisys ClearPath Dorado používají jejich doplněk.

Dějiny

Počátky digitální výpočetní techniky byly poznamenány spoustou konkurenčních představ o hardwarové technologii a matematické technologii (číslovací systémy). Jednou z velkých debat byl formát záporných čísel, někteří špičkoví odborníci té doby měli velmi silné a odlišné názory. Jeden tábor podporoval doplněk dvou , systém, který je dnes dominantní. Doplněk podporovaný dalším táborem, kde je jakákoli kladná hodnota převedena na záporný ekvivalent převrácením všech bitů ve slově. Třetí skupina podporovala „znaménko a velikost“ (velikost znaménka), kde se hodnota změní z kladné na zápornou jednoduše přepnutím bitu znaménka (vyššího řádu) slova.

Pro každý ze systémů existovaly argumenty pro i proti. Znaménko a velikost umožnily snadnější trasování výpisů paměti (běžný proces v šedesátých letech minulého století), protože malé číselné hodnoty používají méně než 1 bit. Interně tyto systémy prováděly matematiku komplementu, takže čísla musela být převedena na hodnoty komplementu těch, které byly přeneseny z registru do matematické jednotky, a poté převedeny zpět na znaménkovou velikost, když byl výsledek přenesen zpět do registru. Elektronika vyžadovala více bran než ostatní systémy - což byl klíčový problém, když byly náklady a balení diskrétních tranzistorů kritické. Společnost IBM byla jedním z prvních příznivců velikosti znaménka, přičemž nejznámějšími systémy, které ji používaly, byly počítače řady 704 , 709 a 709x .

Onesův doplněk umožňoval poněkud jednodušší návrhy hardwaru, protože nebylo nutné převádět hodnoty při předávání do a z matematické jednotky. Ale také sdílel nežádoucí charakteristiku se znaménkovou velikostí-schopnost reprezentovat zápornou nulu (-0). Záporná nula se chová přesně jako kladná nula; při použití jako operand v jakémkoli výpočtu bude výsledek stejný, ať už je operand kladná nebo záporná nula. Nevýhodou však je, že existence dvou forem stejné hodnoty vyžaduje při kontrole rovnosti s nulou spíše dvě než jediné srovnání. Odečtení doplňků může také vést k půjčce typu end-around (popsané níže). Lze tvrdit, že to logiku sčítání/odčítání komplikuje nebo že je to jednodušší, protože odčítání vyžaduje jednoduše invertování bitů druhého operandu při jeho předávání do sčítače. PDP-1 , série CDC 160 , CDC 3000 series, CDC 6000 série , UNIVAC 1100 série, a Linku doplňkem znázornění použití počítače ty.

Doplněk Two je nejsnadněji implementovatelný v hardwaru, což může být hlavním důvodem jeho široké popularity. Procesory na počátečních sálových počítačích často sestávaly z tisíců tranzistorů - eliminace významného počtu tranzistorů byla značná úspora nákladů. Sálové počítače, jako je IBM System/360 , řada GE-600 a PDP-6 a PDP-10, používají dva doplňky, stejně jako minipočítače jako PDP-5 a PDP-8 a PDP-11 a VAX . Architekti raných procesorů založených na integrovaných obvodech ( Intel 8080 atd.) Se rozhodli použít matematiku komplementu dvou. Jak pokročila technologie IC, prakticky všichni přijali technologii komplementu dvou. Oba procesory x86 , m68k , Power ISA , MIPS , SPARC , ARM , Itanium , PA-RISC a DEC Alpha jsou jejich doplňkem.

Podepsaná reprezentace velikosti

Tato reprezentace se také nazývá reprezentace „znaménko – velikost“ nebo „znaménko a velikost“. V tomto přístupu je znak čísla reprezentován znaménkovým bitem : nastavením tohoto bitu (často nejvýznamnějšího bitu ) na 0 pro kladné číslo nebo kladnou nulu a nastavením na 1 pro záporné číslo nebo zápornou nulu. Zbývající bity v čísle udávají velikost (nebo absolutní hodnotu ). Například v osmibitovém bajtu představuje velikost pouze sedm bitů, které se mohou pohybovat od 0000000 (0) do 1111111 (127). Čísla v rozsahu od −127 ₁₀ do +127 ₁₀ lze tedy reprezentovat, jakmile je přidán znaménkový bit (osmý bit). Například −43 ₁₀ zakódovaný v osmibitovém bajtu je 1 0101011, zatímco 43 ₁₀ je 0 0101011. Používání reprezentace podepsané velikosti má mnoho důsledků, což ztěžuje jejich implementaci:

Existují dva způsoby, jak reprezentovat nulu, 00000000 (0) a 10000000 ( -0 ).
Sčítání a odčítání vyžaduje různé chování v závislosti na znaménkovém bitu, zatímco něčí doplněk může ignorovat znaménkový bit a provádět pouze koncový přenos a doplněk dvou může ignorovat znaménkový bit a záviset na chování přetečení.
Porovnání také vyžaduje kontrolu znaménkového bitu, zatímco v doplňku dvou lze jednoduše odečíst dvě čísla a zkontrolovat, zda je výsledek kladný nebo záporný.
Minimální záporné číslo je −127 místo −128 v případě dvojkového doplňku.

Tento přístup je přímo srovnatelný s běžným způsobem zobrazování znaménka (umístění „+“ nebo „ -“ vedle velikosti čísla). Některé rané binární počítače (např. IBM 7090 ) používají tuto reprezentaci, možná kvůli jejímu přirozenému vztahu k běžnému používání. Signovaná velikost je nejběžnějším způsobem, jak reprezentovat význam v hodnotách s plovoucí desetinnou čárkou .

Jeden doplněk

Doplněk osmi bitů
Binární hodnota	Interpretace komplementu	Nepodepsaný výklad
00000000	+0	0
00000001	1	1
⋮	⋮	⋮
01111101	125	125
01111110	126	126
01111111	127	127
10 000 000	−127	128
10000001	−126	129
100 000 10	−125	130
⋮	⋮	⋮
11111101	−2	253
11111110	-1	254
11111111	−0	255

Alternativně lze k reprezentaci záporných čísel použít systém známý jako jejich doplněk. Komplementární forma záporného binárního čísla se na něj bitově NEPOUŽÍVÁ , tj. „Doplněk“ jeho kladného protějšku. Stejně jako reprezentace znaménka a velikosti má jejich doplněk dvě reprezentace 0: 00000000 (+0) a 11111111 ( -0 ).

Například, forma komplementu těch 00101011 (43 ₁₀ ) se stane 11010100 (-43 ₁₀ ). Rozsah podepsaných čísel pomocí jejich doplňku je reprezentován - (2 ^{N −1} - 1) až (2 ^{N −1} - 1) a ± 0. Konvenční osmibitový bajt je −127 ₁₀ až +127 ₁₀ s nulou buď 00000000 (+0) nebo 11111111 (-0).

Chcete-li přidat dvě čísla reprezentovaná v tomto systému, jeden provede konvenční binární sčítání, ale pak je nutné provést end-around carry : to znamená, přidat jakékoli výsledné carry zpět do výsledného součtu. Chcete -li zjistit, proč je to nutné, zvažte následující příklad ukazující případ přidání −1 (11111110) do +2 (00000010):

    binary    decimal
   11111110     −1
+  00000010     +2
───────────     ──
 1 00000000      0   ← Not the correct answer
          1     +1   ← Add carry
───────────     ──
   00000001      1   ← Correct answer

V předchozím příkladu dává první binární sčítání 00000000, což je nesprávné. Správný výsledek (00000001) se zobrazí pouze tehdy, když je zpět přidán přenos.

Poznámka k terminologii: systém se označuje jako „doplněk, protože ty“ negace z kladné hodnoty x (zástupce jako bitové NOT o x ) se může také vytvořit odečtením x od těch komplement zastoupení nula, která je dlouhý sled jedniček (-0). Aritmetika dvojky komplementu na druhé straně tvoří negaci x odečtením x od jedné velké mocniny dvou, která je shodná s +0. Reprezentace komplementu jedničky a dvojky komplementu se stejnou zápornou hodnotou se tedy bude lišit o jednu.

Všimněte si toho, že reprezentaci záporného čísla komplementu jedniček lze získat z reprezentace znaménkové velikosti pouze bitovým doplňováním velikosti (převrácením všech bitů po prvním). Například desítkové číslo −125 s jeho reprezentací 11111101 se znaménkovou velikostí může být reprezentováno ve formě komplementu jako 10000010.

Doplněk dvou

Doplněk osmibitových dvojek
Binární hodnota	Interpretace dvojkového doplňku	Nepodepsaný výklad
00000000	0	0
00000001	1	1
⋮	⋮	⋮
01111110	126	126
01111111	127	127
10 000 000	−128	128
10000001	−127	129
100 000 10	−126	130
⋮	⋮	⋮
11111110	−2	254
11111111	-1	255

Problémy vícenásobné reprezentace 0 a potřeba end-around carry obchází systém nazývaný dvojkový doplněk . V doplňku dvou jsou záporná čísla reprezentována bitovým vzorem, který je o jeden větší (v znaménku) než doplněk kladné hodnoty.

Ve dvojkovém doplňku je pouze jedna nula, reprezentovaná 00000000. Negování čísla (ať už záporného nebo kladného) se provádí převrácením všech bitů a přidáním jednoho k tomuto výsledku. To skutečně odráží kruhovou strukturu na všechna celá čísla modulo 2 ^N : . Přidání dvojice celých čísel dvou doplňků je stejné jako přidání dvojice nepodepsaných čísel (kromě detekce přetečení , pokud je to provedeno); totéž platí pro odčítání a dokonce pro N nejnižších významných bitů produktu (hodnota násobení). Například sčítání 127 a −128 s komplementem dvou dává stejný binární bitový vzor jako bez znaménka sčítání 127 a 128, jak je vidět z 8-bitové dvojkové komplementární tabulky. ${\ Displaystyle \ mathbb {Z} /2^{N} \ mathbb {Z}}$

Jednodušší způsob, jak získat negaci čísla ve dvojkovém doplňku, je následující:

	Příklad 1	Příklad 2
1. Začněte zprava, najděte první „1“	0010100 1	00101 1 00
2. Invertujte všechny bity nalevo od „1“	1101011 1	11010 : 100

Metoda dvě:

Invertujte všechny bity přes číslo
Přidejte jeden

Příklad: pro +2, což je 00000010 v binárním formátu (znak ~ je operátor C bitový NOT , takže ~ X znamená „invertovat všechny bity v X“):

~ 00000010 → 11111101
11111101 + 1 → 11111110 (−2 ve dvojkovém doplňku)

Ofsetový binární soubor

Osmbitový přebytek-128
Binární hodnota	Přebytek-128 interpretace	Nepodepsaný výklad
00000000	−128	0
00000001	−127	1
⋮	⋮	⋮
01111111	-1	127
10 000 000	0	128
10000001	1	129
⋮	⋮	⋮
11111111	+127	255

V binárním ofsetu (také nazývaném přebytek- K nebo zkreslená reprezentace) je podepsané číslo n reprezentováno bitovým vzorem odpovídajícím číslu bez znaménka n + K , přičemž K je předpínací hodnota nebo offset . 0 je tedy reprezentováno K a- K je reprezentováno bitovým vzorcem s nulovým počtem bitů. To lze chápat jako mírnou modifikaci a zobecnění výše uvedeného komplementu dvou, což je prakticky nadbytečná (2 ^{N -1} ) reprezentace s negovaným nejvýznamnějším bitem .

Předpojaté reprezentace se nyní primárně používají pro exponent čísel s plovoucí desetinnou čárkou . Standard IEEE 754 s plovoucí desetinnou čárkou definuje pole exponentu čísla s jedinou přesností (32bitové) jako pole s 8bitovým přebytkem -127 . Pole exponentu s dvojitou přesností (64bitové) je pole s 11bitovým přebytkem-1023 ; viz exponent zaujatost . Měl také použití pro binárně kódovaná desetinná čísla jako přebytek-3 .

Základ −2

V konvenčních binárních číselných soustavách je základna nebo radix 2; bit zcela vpravo tedy představuje 2 ⁰ , další bit představuje 2 ¹ , další bit 2 ² atd. Je však také možný systém binárních čísel se základnou −2. Pravý bit představuje (−2) ⁰ = +1 , další bit představuje (−2) ¹ = −2 , další bit (−2) ² = +4 atd., Se střídavým znaménkem. Čísla, která lze reprezentovat čtyřmi bity, jsou uvedena v níže uvedené srovnávací tabulce.

Rozsah čísel, která lze reprezentovat, je asymetrický. Pokud má slovo sudý počet bitů, velikost největšího záporného čísla, které lze reprezentovat, je dvakrát větší než největší kladné číslo, které lze zastoupit, a naopak, pokud má slovo lichý počet bitů.

Srovnávací tabulka

Následující tabulka ukazuje kladná a záporná celá čísla, která lze vyjádřit pomocí čtyř bitů.

Čtyřbitové celočíselné reprezentace
Desetinný	Nepodepsaný	Znamení a velikost	Jeden doplněk	Doplněk dvou	Přebytek-8 (předpojatý)	Základ −2
+16	N/A	N/A	N/A	N/A	N/A	N/A
+15	1111	N/A	N/A	N/A	N/A	N/A
+14	1110	N/A	N/A	N/A	N/A	N/A
+13	1101	N/A	N/A	N/A	N/A	N/A
+12	1100	N/A	N/A	N/A	N/A	N/A
+11	1011	N/A	N/A	N/A	N/A	N/A
+10	1010	N/A	N/A	N/A	N/A	N/A
+9	1001	N/A	N/A	N/A	N/A	N/A
+8	1000	N/A	N/A	N/A	N/A	N/A
+7	0111	0111	0111	0111	1111	N/A
+6	0110	0110	0110	0110	1110	N/A
+5	0101	0101	0101	0101	1101	0101
+4	0100	0100	0100	0100	1100	0100
+3	0011	0011	0011	0011	1011	0111
+2	0010	0010	0010	0010	1010	0110
+1	0001	0001	0001	0001	1001	0001
+0	0000	0000	0000	0000	1000	0000
−0	0000	1000	1111	0000	1000	0000
-1	N/A	1001	1110	1111	0111	0011
−2	N/A	1010	1101	1110	0110	0010
−3	N/A	1011	1100	1101	0101	1101
−4	N/A	1100	1011	1100	0100	1100
−5	N/A	1101	1010	1011	0011	1111
−6	N/A	1110	1001	1010	0010	1110
−7	N/A	1111	1000	1001	0001	1001
−8	N/A	N/A	N/A	1000	0000	1000
−9	N/A	N/A	N/A	N/A	N/A	1011
−10	N/A	N/A	N/A	N/A	N/A	1010
−11	N/A	N/A	N/A	N/A	N/A	N/A

Stejná tabulka, při pohledu z „vzhledem k těmto binárním bitům, jaké je číslo interpretované reprezentačním systémem“:

Binární	Nepodepsaný	Znamení a velikost	Jeden doplněk	Doplněk dvou	Přebytek-8	Základ −2
0000	0	0	0	0	−8	0
0001	1	1	1	1	−7	1
0010	2	2	2	2	−6	−2
0011	3	3	3	3	−5	-1
0100	4	4	4	4	−4	4
0101	5	5	5	5	−3	5
0110	6	6	6	6	−2	2
0111	7	7	7	7	-1	3
1000	8	−0	−7	−8	0	−8
1001	9	-1	−6	−7	1	−7
1010	10	−2	−5	−6	2	−10
1011	11	−3	−4	−5	3	−9
1100	12	−4	−3	−4	4	−4
1101	13	−5	−2	−3	5	−3
1110	14	−6	-1	−2	6	−6
1111	15	−7	−0	-1	7	−5

Jiné systémy

„Zig-zag encoding“ Google Protocol Buffers je systém podobný znaku a velikosti, ale používá nejméně významný bit k reprezentaci znaku a má jedinou reprezentaci nuly. To umožňuje efektivní použití kódování množství proměnné délky určeného pro nezáporná (bez znaménka) celá čísla pro celá čísla se znaménkem.

Podobná metoda se používá ve standardech komprese videa kódování videa H.264/MPEG-4 AVC a H.265 s vysokou účinností pro rozšíření exponenciálního Golombova kódování na záporná čísla. V tomto rozšíření je nejméně významný bit téměř znaménkový bit; nula má stejný nejméně významný bit (0) jako všechna záporná čísla. Tato volba má za následek, že kladné číslo reprezentovatelné největší velikostí je o jedno vyšší než záporné číslo největší velikosti, na rozdíl od cik-cakového kódování doplňků dvou nebo Protokolů vyrovnávacích pamětí.

Dalším přístupem je dát každé číslici znak, čímž se získá reprezentace podepsané číslice . Například v roce 1726 John Colson prosazoval redukci výrazů na „malá čísla“, číslice 1, 2, 3, 4 a 5. V roce 1840 také Augustin Cauchy vyjádřil přednost takto upraveným desetinným číslům, aby se snížily chyby ve výpočtu.

Viz také

Reference

Ivan Flores, Logika počítačové aritmetiky , Prentice-Hall (1963)
Israel Koren, počítačové aritmetické algoritmy , AK Peters (2002), ISBN 1-56881-160-8

Languages

In other projects