Existují tři různé způsoby, jak reprezentovat celé číslo se znaménkem (článek) . a: bit se znaménkem, b: doplněk 1 a c: doplněk 2. Pokusme se pochopit, jak tyto metody vznikly a proč je doplněk 2 preferován před ostatními.

Jak víme, data jsou uložena v bitech. Jak můžeme uložit celé číslo se znaménkem do paměti? Abychom tento problém vyřešili, nejprve vyvineme naivní řešení a poté jej budeme opakovat, dokud nebudeme mít nejlepší řešení pro náš problém.

a) Podepsaný bit

Při pokusu o uložení celého čísla se znaménkem se zdá být zřejmé, že ponecháte bit nejvíce vlevo pro znaménko a zbývající bity použijete ke skutečnému uložení hodnot. Například: ve 4bitovém systému bude první bit zleva rezervován pro znaménko (0 představuje kladné, zatímco 1 představuje záporné) a další 3 bity budou použity k uložení hodnot. Podobně v 8bitovém systému bude první bit zleva použit pro znaménko a zbývajících 7 bude použito pro hodnoty.

Pomocí tohoto přístupu jsme úspěšně schopni reprezentovat celé číslo se znaménkem. Ale když to analyzujeme podrobněji, můžeme pozorovat následující nevýhody:

1) Dvě reprezentace nuly:

Ve 4bitovém systému bychom měli být schopni uložit 16 (24) hodnot, ale +1 až +7 a -1 až -7 je pouze 14 hodnot. Kde jsou zbývající dvě hodnoty? Když tabulku pozorně sledujeme, zjistíme, že tyto dvě hodnoty konvergují k 0. Máme tedy dvě zobrazení nuly, tedy jedno zobrazení pro +0 a druhé pro -0.

Jsou ale dvě reprezentace 0 velkým problémem? No a co? Místo 16 jedinečných hodnot jsme schopni uložit pouze 15 hodnot. Můžeme si dovolit snížit rozsah o 1, ne? Pro vývojáře softwaru to nemusí být důležité, ale pro návrháře obvodů může být velmi frustrující nejprve zkontrolovat, zda je hodnota +0, a poté zkontrolovat, zda je -0.

2) Rozšíření se znaménkem nefunguje pro záporná čísla:

Velikost dat rychle roste. Nějaký čas potřebujeme rozšířit bitový systém, abychom mohli zvětšit rozsah dat, která lze uložit. V roce 2014 video Gangnam Style překročilo limit zobrazení YouTube a donutil YouTube upgradovat počet zhlédnutí z 32bitových na 64bitové celé číslo se znaménkem. Podobně 32bitové unixové hodiny přetečou 19. ledna 2038, protože zaznamenávají čas v sekundách ve 32bitovém celém čísle se znaménkem.

Je tedy stejně důležité, aby byl náš reprezentační systém snadno rozšiřitelný, což u tohoto reprezentačního systému není možné.

3) Binární sčítání nefunguje:

Zkusme sečíst dvě binární čísla:

Proč zde nefunguje jednoduché binární sčítání? Důvodem je, že bit znaménka (nejvíce vlevo) není obyčejný bit a není součástí skutečného čísla. Představte si situaci, kdy je třeba navrhnout hardwarové obvody tak, aby ignorovaly znaménkový bit, aby bylo možné provést sčítání, a poté připojit znaménkový bit.

Takže to byl naivní způsob, jak reprezentovat celé číslo se znaménkem. Hlavním problémem tohoto přístupu je, že jsme namapovali záporná čísla směrem dolů. Pokud změníme náš systém mapování tak, aby byly shora dolů, některé z výše uvedených problémů budou vyřešeny.

b) 1's Co implementovat

Pokud přemapujeme naše záporná čísla shora dolů, dostaneme následující binární tabulku:

Jak získat binární reprezentaci celého čísla v metodě doplňku 1?

• Kladná čísla jsou reprezentována podobně jako metoda celých čísel se znaménkem
• Záporná čísla jsou reprezentována invertováním každého bitu odpovídajícího kladného čísla (invertování lze snadno provést pomocí brány NOT během návrhu hardwaru)

Pojďme to podrobně analyzovat, abychom zjistili, zda jsme dosáhli nějakého zlepšení.

1) Dvě reprezentace nuly:

V tomto přístupu také máme dvě reprezentace nuly.

2) Rozšíření se znaménkem nefunguje pro záporná čísla:

Podepsané rozšíření funguje perfektně pro záporná čísla.

3) Binární sčítání funguje s upravenými pravidly:

Odpověď není vždy správná, ale je velmi blízko správné odpovědi. Můžeme to udělat, pokud budeme dodržovat pravidlo, že pokud jste vytvořili přenos vpřed na svém nejvíce levém bitu, nevyhazujte jej, místo toho jej vraťte zpět a přidejte jej k nejvíce pravému bitu.

Metoda doplňku 1 je rozhodně lepší než bit se znaménkem. Naše hlavní obavy jsou vyřešeny, ale zůstávají problémem (mají dvě reprezentace nuly) a náš hack v binárním sčítání poskytuje vodítka ke zlepšení metody komplementu 1. Pojďme si ty věty přeformulovat, aby to bylo jednodušší.

• Máme navíc zastoupení nuly, což je zbytečné
• Při sčítání dvou binárních čísel, pokud máme přenos v levém nejvíce bitu, musíme k výsledku přidat +1, tj. správnou odpověď lze najít přechodem dolů na další řádek v binární tabulce.

Oba nás nasměrují, že extra reprezentace nuly je hlavní příčinou problému. Odeberme tedy tuto nulu navíc a přesuňte všechny záporné hodnoty na další řádek (-7 se přesune z I -> J, -6 se přesune z J -> K a tak dále…)

c) Doplněk 2

Když odstraníme -0 z tabulky doplňků 1 a posuneme všechny záporné hodnoty o jeden řádek níže, dostaneme následující tabulku, která se nazývá doplněk 2:

Jak získat binární reprezentaci celého čísla v metodě komplementu 2?

• Kladná čísla jsou reprezentována podobně jako metoda celých čísel se znaménkem
• Záporná čísla jsou reprezentována invertováním každého bitu odpovídajícího kladného čísla a poté k němu přičtením 1 bitu

1) Jedno zobrazení nuly:

Nyní máme pouze jednu reprezentaci nuly a ta nám umožňuje ukládat celkem 16 jedinečných hodnot (+0 až +7 a -1 až -8).

2) Rozšíření se znaménkem funguje pro záporná čísla:

Podepsané rozšíření funguje perfektně pro záporná čísla.

3) Binární sčítání:

4) První bit je bit se znaménkem:

Doplněk 2 má tu příjemnou vlastnost, že první bit je znaménkový bit, protože všechny kladné začínají 0, zatímco všechny záporné 1.

5) Kontrola přetečení paměti:

Při přidávání jsme se ujistili, že naše odpověď je v rámci rozsahu, ale při navrhování hardwaru je třeba detekovat přetečení paměti. Pro návrháře hardwaru bude velmi špatný nápad kontrolovat velikost, aby zachytili přetečení. Metoda doplňku 2 poskytuje velmi jednoduchý způsob, jak detekovat přetečení paměti. já f přenos do bitu se znaménkem se nerovná provádění bitu se znaménkem, pak jde o přetečení paměti tj. pokud přenos do bitu se znaménkem je 0, ale provádění je 1 nebo pokud přenos 1, ale provádění je 0, pak se jedná o přetečení paměti.

rozvětvené stromy