Doplněk dvou - Two's complement

Dvojkový doplněk je matematická operace na binárních číslech a je příkladem radixového doplňku . Používá se při výpočtu jako metoda reprezentace podepsaných čísel .

Dvojkový doplněk N -bitového čísla je definován jako jeho doplněk vzhledem k 2 N ; součet čísla a její komplement dvojkového je 2 N . Například pro tříbitové číslo 010 2 je dvojkový doplněk 110 2 , protože 010 2 + 110 2 = 1000 2 = 8 10, což se rovná 2 3 . Doplněk těchto dvou se vypočítá převrácením bitů a přidáním jednoho.

Tříbitová celá čísla se znaménkem
Desetinná
hodnota
Dvojkových doplňků
reprezentace
0 000
1 001
2 010
3 011
−4 100
−3 101
−2 110
-1 111
Osmbitová celá čísla se znaménkem
Desetinná
hodnota
Dvojkových doplňků
reprezentace
0 0000 0000
1 0000 0001
2 0000 0010
126 0111 1110
127 0111 1111
−128 1 000 0000
−127 1000 0001
−126 1000 0010
−2 1111 1110
-1 1111 1111

Doplněk dvojky je nejběžnější metodou reprezentace celých čísel se znaménkem na počítačích a obecněji binárních hodnot s pevným bodem . V tomto schématu, pokud binární číslo 010 2 kóduje podepsané celé číslo 2 10 , pak jeho dvojkový doplněk, 110 2 , kóduje inverzní: −2 10 . Jinými slovy, znaménko většiny celých čísel (kromě jednoho z nich) lze v tomto schématu obrátit tím, že vezmeme jejich binární reprezentaci. Tabulky vpravo ilustrují tuto vlastnost.

Ve srovnání s jinými systémy pro reprezentaci podepsaných čísel ( např. Doplněk jedniček ) má dvojkový doplněk tu výhodu, že základní aritmetické operace sčítání , odčítání a násobení jsou totožné s operacemi pro binární čísla bez znaménka (pokud jsou vstupy zastoupeny v stejný počet bitů jako výstup a jakékoli přetečení nad rámec těchto bitů je z výsledku vyřazeno). Tato vlastnost usnadňuje implementaci systému, zejména pro aritmetiku s vyšší přesností. Na rozdíl od komplementových systémů jedničky nemá komplement dvou reprezentaci záporné nuly , a proto netrpí souvisejícími obtížemi.

Pohodlně je dalším způsobem, jak najít dva komplementy čísla, vzít jeho komplement a přidat jeden: součet čísla a jeho komplementu je všechny '1' bity, nebo 2 N - 1 ; a podle definice je součet množství a jeho dvojkového doplňku je 2 N .

Dějiny

Způsob doplňků dlouho byl použit k provedení odčítání v desítkové soustavě přidáním strojů a mechanických kalkulátorů . John von Neumann navrhl použití dvojkové binární reprezentace komplementu ve svém prvním návrhu zprávy o návrhu EDVAC pro elektronický digitální počítač s uloženým programem v roce 1945 . EDSAC z roku 1949 , který byl inspirován Prvním návrhem , používal reprezentaci dvojkových doplňků binárních čísel.

Mnoho raných počítačů, včetně CDC 6600 , LINC , PDP-1 a UNIVAC 1107, používá zápis komplementu ; pokračovali v tom potomci UNIVAC 1107, řady UNIVAC 1100/2200 . Tyto řady IBM 700/7000 vědecké stroje používat znak / magnitudy notaci, s výjimkou indexu registrů, které jsou dvě části. Počáteční komerční komplementární počítače zahrnují Digital Equipment Corporation PDP-5 a 1963 PDP-6 . System / 360 , který byl zaveden v roce 1964 IBM , pak dominantní hráč v počítačovém průmyslu, udělal dva se doplňují nejpoužívanější binární reprezentaci v počítačovém průmyslu. První minipočítač, PDP-8 představený v roce 1965, používá aritmetiku dvou komplementů, stejně jako Data General Nova z roku 1969, PDP-11 z roku 1970 a téměř všechny následující minipočítače a mikropočítače.

Převod z reprezentace komplementu dvou

Číselný systém dvojného komplementu kóduje kladná a záporná čísla v reprezentaci binárních čísel. Váha každého bitu je mocnina dvou, s výjimkou nejvýznamnějšího bitu , jehož váha je záporem odpovídající síly dvou.

Hodnota  w z N- bitovým celé číslo se vypočítá podle následujícího vzorce:

Nejvýznamnější bit určuje znaménko čísla a někdy se nazývá znaménkový bit . Na rozdíl od reprezentace znaménka a velikosti má bit znaménka také váhu- (2 N  -1 ) uvedenou výše. Pomocí N bitů lze reprezentovat všechna celá čísla od - (2 N  - 1 ) do 2 N  - 1 - 1 .

Převod na reprezentaci komplementu dvou

V zápisu komplementu dvou je nezáporné číslo reprezentováno jeho obyčejnou binární reprezentací ; v tomto případě je nejvýznamnější bit 0. Ačkoli rozsah reprezentovaných čísel není stejný jako u binárních čísel bez znaménka. Například 8bitové číslo bez znaménka může představovat hodnoty 0 až 255 (11111111). 8bitové číslo komplementu dvojky však může představovat pouze kladná celá čísla od 0 do 127 (01111111), protože zbytek bitových kombinací s nejvýznamnějším bitem jako '1' představuje záporná celá čísla -1 až -128.

Operace komplementu těchto dvou je aditivní inverzní operace, takže záporná čísla jsou reprezentována komplementem absolutní hodnoty .

Z doplňku těch

Chcete -li získat dvojku se záporným binárním číslem, jsou bity invertovány nebo „převráceny“ pomocí bitové operace NOT ; hodnota 1 se pak přičte k výsledné hodnotě, přičemž se ignoruje přetečení, ke kterému dochází, když se vezme doplněk obou 0.

Například pomocí 1 bajtu (= 8 bitů) je desetinné číslo 5 reprezentováno

0000 0101 2

Nejvýznamnější bit je 0, takže vzor představuje nezápornou hodnotu. Chcete-li převést na −5 v zápisu komplementu dvou, nejprve jsou bity invertovány, to znamená: 0 se stane 1 a 1 se stane 0:

1111 1010 2

V tomto okamžiku je reprezentace doplňkem desítkové hodnoty −5. K získání těchto dvou doplňků je k výsledku přidána 1, která dává:

1111 1011 2

Výsledkem je binární číslo se znaménkem představující desítkovou hodnotu −5 ve formě dvojkového doplňku. Nejvýznamnější bit je 1, takže reprezentovaná hodnota je záporná.

Doplnění těchto dvou záporných čísel je odpovídající kladnou hodnotou, s výjimkou jednoho zvláštního případu. Invertováním bitů −5 (výše) například získáte:

0000 0100 2

A přidáním jednoho získáte konečnou hodnotu:

0000 0101 2

Podobně je doplněk nuly obou nulový: invertování dává všechny jedničky a přidání jednoho změní jedničky zpět na nuly (protože přetečení je ignorováno).

Dvojkový doplněk nejvíce záporného čísla, který lze reprezentovat (např. Jednička jako nejvýznamnější bit a všechny ostatní bity nula), je sám. Existuje tedy „extra“ záporné číslo, pro které dvojkový doplněk nedává negaci, viz § Nejvíce záporné číslo níže.

Odečtení od 2 N.

Součet čísla a jeho doplňku je N -bitové slovo se všemi 1 bity, což je (čtení jako binární číslo bez znaménka) 2 N -1 . Pak se přidá číslo na dvě části výsledků v N nejnižšími bity nastavenými na 0 ° C a nést bit 1, podle toho, které má hmotnost (čtení jako bez znaménka binární čísla) 2 N . V binární aritmetice bez znaménka tedy hodnota záporného čísla x * kladného x dvojitého komplementu splňuje rovnost x * = 2 N - x .

Chcete-li například najít 4bitovou reprezentaci −5 (indexy označují základ reprezentace ):

x = 5 10 tedy x = 0101 2

Proto s N = 4 :

x * = 2 N - x = 2 4 - 5 10 = 16 10 - 5 10 = 10000 2 - 0101 2 = 1011 2

Výpočet lze provést zcela na základně 10, převedením na základnu 2 na konci:

x * = 2 N - x = 2 4 - 5 10 = 11 10 = 1011 2

Práce od LSB k MSB

Zkratkou pro ruční převod binárního čísla na jeho doplněk je začít na nejméně významném bitu (LSB) a zkopírovat všechny nuly, pracující od LSB směrem k nejvýznamnějšímu bitu (MSB), dokud není dosaženo první 1; pak zkopírujte tuto 1 a převraťte všechny zbývající bity (ponechte MSB jako 1, pokud bylo počáteční číslo v reprezentaci znaménka a velikosti). Tato zkratka umožňuje člověku převést číslo na jeho dvojkový doplněk, aniž by nejprve vytvořil doplněk jeho jedniček. Například: ve dvojkové reprezentaci komplementu je negace „0011 1100“ „1100 0 100 “, kde podtržené číslice nebyly kopírováním změněny (zatímco ostatní číslice byly převráceny).

V počítačových obvodech není tato metoda rychlejší než metoda „doplnit a přidat jednu“; obě metody vyžadují postupnou práci zprava doleva, šíření logických změn. Metodu doplňování a přidávání lze urychlit standardním obvodem pro sčítání do budoucna ; metodu LSB směrem k MSB lze zrychlit podobnou logickou transformací.

Rozšíření znamení

Signální bitové opakování v 7- a 8bitových celých číslech pomocí dvojkového doplňku
Desetinný 7bitový zápis 8bitový zápis
−42  1010110 1101 0110
42  0101010 0010 1010

Při převádění dvojkového doplňkového čísla s určitým počtem bitů na jedno s více bity (např. Při kopírování z 1bajtové proměnné do 2bajtové proměnné) musí být nejvýznamnější bit opakován ve všech extra bitech . Některé procesory to dělají v jediné instrukci; na ostatních procesorech musí být použit podmíněný kód následovaný kódem pro nastavení příslušných bitů nebo bytů.

Podobně, když je číslo dvojkového doplňku posunuto doprava, musí být zachován nejvýznamnější bit, který obsahuje velikost a informace o znaménku. Při posunu doleva se ale posunuje 0. Tato pravidla zachovávají běžnou sémantiku, že posuny doleva vynásobí číslo dvěma a posuny doprava rozdělí číslo dvěma.

Jak řazení, tak zdvojnásobení přesnosti jsou pro některé multiplikační algoritmy důležité. Všimněte si toho, že na rozdíl od sčítání a odčítání se rozšíření šířky a posunutí doprava provádějí odlišně pro čísla se znaménkem a bez znaménka.

Nejvíce záporné číslo

Pouze s jednou výjimkou, počínaje libovolným číslem v reprezentaci dvou doplňků, pokud jsou všechny bity převráceny a přidána 1, získá se reprezentace záporného čísla tohoto komplementu. Kladná 12 se stává zápornou 12, kladná 5 se stává zápornou 5, nula se stává nulou (+přetečení) atd.

Výsledkem dvojice -128 je stejné 8bitové binární číslo.
−128 1 000 0000
invertovat bity 0111 1111
přidat jeden 1 000 0000

Vezmeme -li dvojici jako doplněk minimálního počtu v rozsahu, nebude to mít požadovaný účinek negace čísla. Například dvojkový doplněk −128 v 8bitovém systému je −128. Ačkoli očekávaný výsledek z negace −128 je +128, neexistuje reprezentace +128 s 8bitovým dvojkovým doplňkovým systémem, a proto je ve skutečnosti nemožné reprezentovat negaci. Všimněte si, že komplement těchto dvou je stejný počet je detekován jako podmínka přetečení, protože došlo k přenosu, ale ne mimo nejvýznamnější bit.

Tento jev je v zásadě o matematice binárních čísel, nikoli o podrobnostech reprezentace jako doplňku dvou. Matematicky je to komplementární ke skutečnosti, že záporná hodnota 0 je opět 0. Pro daný počet bitů k existuje sudý počet binárních čísel 2 k , přičemž negativy jsou skupinovou akcí (skupiny řádu 2) na binární čísla, a protože nulová oběžná dráha má pořadí 1, musí alespoň jedno další číslo mít oběžnou dráhu řádu 1, aby se pořadí oběžných drah sčítalo s pořadím sady. Při přijímání negativů tedy musí být nějaké jiné číslo invariantní (formálně podle věty o stabilizaci oběžné dráhy ). Geometricky lze na k -bitová binární čísla pohlížet jako na cyklickou skupinu , kterou lze zobrazit jako kruh (nebo správně pravidelný 2 k -gon), přičemž záporné hodnoty jsou odrazem, který opravuje prvky dělení řádu 2: 0 a opačný bod, nebo vizuálně zenit a nejnižší hodnota.

Přítomnost nejnegativnějšího čísla může vést k neočekávaným programovacím chybám, kde výsledek má neočekávané znaménko, nebo vede k neočekávané výjimce přetečení nebo vede ke zcela zvláštnímu chování. Například,

  • operátor unární negace nesmí změnit znaménko nenulového čísla. např. - ( - 128) → −128.
  • implementace absolutní hodnoty může vrátit záporné číslo. např. abs (−128) → −128.
  • Stejně tak nemusí fungovat násobení −1 podle očekávání. např. (−128) × (−1) → −128.
  • Dělení −1 může způsobit výjimku (jako je ta způsobená dělením 0). Tuto výjimku může vyvolat i výpočet zbytku (nebo modulo) pomocí −1. např. (−128) ÷ (−1) → pád, (−128) % (−1) → pád.

V programovacích jazycích C a C ++ jsou výše uvedená chování nedefinovaná a nejen, že mohou vracet podivné výsledky, ale kompilátor může svobodně předpokládat, že programátor zajistil, že se nedefinované výpočty nikdy nestanou, a vyvodit z toho předpoklad. To umožňuje řadu optimalizací, ale také vede k řadě podivných chyb v takto nedefinovaných programech.

Nejnegativnější číslo v doplňku dvou se někdy nazývá „podivné číslo“, protože je to jediná výjimka. Ačkoli je číslo výjimkou, je platným číslem v systémech doplňků běžných dvou. Všechny aritmetické operace s ním fungují jak jako operand, tak (pokud nedojde k přetečení) jako výsledek.

Proč to funguje?

Vzhledem k množině všech možných N -bitových hodnot můžeme nižší (o binární hodnotu) přiřadit celá čísla od 0 do (2 N  -1 -1) včetně a horní polovinu o -2 N  -1 na −1 včetně. Horní polovinu (opět binární hodnotou) lze použít k reprezentaci záporných celých čísel od −2 N  - 1 do −1, protože pod přídavným modulem 2 N se chovají stejně jako tato záporná celá čísla. To znamená, že protože i + j mod 2 N = i + ( j + 2 N ) mod 2 N libovolná hodnota v sadě {  j + k  2 N | k je celé číslo}  lze použít místo  j .

Například s osmi bity jsou nepodepsané bajty 0 až 255. Odečtením 256 od horní poloviny (128 až 255) se získají podepsané bajty −128 až −1.

Vztah k dvojkový doplněk je realizováno za zmínku, že 256 = 255 + 1 , a (255 - x ) je jedničkový doplněkx .

Několik speciálních čísel k poznámce
Desetinný Binární
127  0111 1111
64  0100 0000
1   0000 0001
0   0000 0000
-1  1111 1111
−64  1100 0000
−127  1000 0001
−128  1 000 0000

Příklad

V tomto podsekci jsou desetinná čísla zakončena desetinnou čárkou „.“

Například 8bitové číslo může představovat pouze každé celé číslo od −128. až 127. včetně, protože (2 8 - 1 = 128.) . -95. modulo 256. odpovídá 161. od

-95. + 256.
= -95. + 255. + 1
= 255 - 95. + 1
= 160. + 1.
= 161.
   1111 1111 255.
 - 0101 1111 - 95.
 ==================
   1010 0000 (doplněk) 160.
 + 1 + 1
 ==================
   1010 0001 (dvojkový doplněk) 161.
Dvojka doplňuje 4bitové celočíselné hodnoty
Doplněk dvou Desetinný
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. 

Systém v zásadě představuje záporná celá čísla tím, že počítá zpět a obtéká se . Hranice mezi kladnými a zápornými čísly je libovolná, ale podle konvence mají všechna záporná čísla bit úplně vlevo ( nejvýznamnější bit ) jedničku. Nejpozitivnější 4bitové číslo je tedy 0111 (7.) a nejnegativnější je 1000 (−8.). Kvůli použití bitu nejvíce vlevo jako znaménkového bitu je absolutní hodnota nejzápornějšího čísla (| -8. | = 8.) příliš velká na to, aby se dala znázornit. Odmítnutí čísla doplňku dvojky je jednoduché: Invertujte všechny bity a přidejte jeden k výsledku. Například negací 1111 dostaneme 0000 + 1 = 1 . Proto 1111 v binárním formátu musí představovat -1 v desítkové soustavě.

Systém je užitečný při zjednodušení implementace aritmetiky na počítačovém hardwaru. Zdá se, že přidání 0011 (3.) do 1111 (−1.) Zpočátku dává nesprávnou odpověď 10010. Hardware však může jednoduše ignorovat bit úplně vlevo a poskytnout správnou odpověď 0010 (2.). Aby bylo možné zachytit operace, jako je součet 0100 a 0100, musí stále existovat kontroly přetečení.

Systém proto umožňuje sčítání záporných operandů bez odčítacího obvodu nebo obvodu, který detekuje znaménko čísla. Navíc tento sčítací obvod může také provádět odčítání tím, že vezme doplněk čísla (viz níže), což vyžaduje pouze další cyklus nebo vlastní sčítací obvod. Aby to provedl, obvod funguje pouze tak, jako by tam byl extra levý nejvíce bit 1.

Aritmetické operace

Přidání

Přidání čísel dvojitého doplňku nevyžaduje žádné speciální zpracování, i když operandy mají opačná znaménka: znaménko výsledku je určeno automaticky. Například přidání 15 a −5:

  11111111 (nést)
   0000 1111 (15)
 + 1111 1011 (−5)
 ============
   0000 1010 (10)

Nebo výpočet 5 - 15 = 5 + (−15):

          1 (nést)
   0000 0101 (5)
 + 1111 0001 (−15)
 ============
   1111 0110 (−10)

Tento proces závisí na omezení na 8 bitů přesnosti; přenos na (neexistující) 9. nejvýznamnější bit je ignorován, což má za následek aritmeticky správný výsledek 10 10 .

Poslední dva bity řádku přenosu (čtení zprava doleva) obsahují zásadní informace: zda výpočet vedl k aritmetickému přetečení , číslo příliš velké na to, aby jej mohl binární systém reprezentovat (v tomto případě větší než 8 bitů). Podmínka přetečení existuje, když se tyto dva poslední bity navzájem liší. Jak bylo uvedeno výše, znaménko čísla je zakódováno v MSB výsledku.

Jinými slovy, pokud jsou levé dva přenosové bity (ty v těchto příkladech úplně vlevo nahoře v horním řádku) oba 1 s nebo obě 0, je výsledek platný; pokud jsou levé dva přenosové bity „1 0“ nebo „0 1“, došlo k přetečení znaménka. Pohodlně může operace XOR na těchto dvou bitech rychle určit, zda existuje stav přetečení. Jako příklad zvažte podepsané 4bitové přidání 7 a 3:

  0111 (nošení)
   0111 (7)
 + 0011 (3)
 =======
   1010 (−6) neplatné!

V tomto případě jsou krajní levý dva (MSB) přenosové bity „01“, což znamená, že došlo k přetečení přídavku dvou komplementů. To znamená, že 1010 2 = 10 10 je mimo povolený rozsah −8 až 7. Výsledek by byl správný, pokud by byl považován za celé číslo bez znaménka.

Obecně lze libovolná dvě N -bitová čísla přidat bez přetečení tak, že nejprve obě rozšíříte na N  + 1 bitů a poté přidáte, jak je uvedeno výše. Výsledek N  + 1 bitů je dostatečně velký na to, aby představoval jakýkoli možný součet ( N = 5 dvojkový doplněk může představovat hodnoty v rozsahu −16 až 15), takže k přetečení nikdy nedojde. Potom je možné, pokud je to žádoucí, 'zkrátit' výsledek zpět na N bitů při zachování hodnoty tehdy a jen tehdy, pokud je vyřazený bit správným rozšířením znaménka zachovaných výsledných bitů. To poskytuje další způsob detekce přetečení - který je ekvivalentní způsobu porovnávání přenosových bitů - ale který může být v některých situacích snáze implementovatelný, protože nevyžaduje přístup k vnitřním součástem přídavku.

Odčítání

Počítače obvykle používají k implementaci odčítání metodu doplňků . Použití doplňků pro odčítání je úzce spjato s používáním doplňků pro reprezentaci záporných čísel, protože kombinace umožňuje všechny znaky operandů a výsledků; přímé odčítání funguje také s čísly dvou doplňků. Stejně jako sčítání, výhodou použití dvojkového doplňku je eliminace zkoumání znaků operandů za účelem určení, zda je nutné sčítání nebo odčítání. Například odečtením −5 od 15 se skutečně přičte 5 k 15, ale to je skryto reprezentací těchto dvou doplňků:

  11110 000 (půjčka)
   0000 1111 (15)
 - 1111 1011 (−5)
 ============
   0001 0100 (20)

Přetečení je detekováno stejným způsobem jako u sčítání, a to zkoumáním dvou nejvíce levých (nejvýznamnějších) bitů výpůjček; pokud se liší, došlo k přetečení.

Dalším příkladem je operace odčítání, kde je výsledek záporný: 15 - 35 = −20:

  11100 000 (půjčka)
   0000 1111 (15)
 - 0010 0011 (35)
 ============
   1110 1100 (−20)

Pokud jde o sčítání, přetečení při odčítání lze zabránit (nebo je detekovat po operaci) prvním rozšířením obou vstupů o další bit.

Násobení

Součin dvou N -bitových čísel vyžaduje, aby 2 N bity obsahovaly všechny možné hodnoty.

Pokud se přesnost dvou operandů pomocí komplementu dvou zdvojnásobí před násobením, správný výsledek poskytne přímá multiplikace (vyřazení všech přebytečných bitů nad tuto přesnost). Vezměte například 6 × (−5) = −30 . Za prvé, přesnost je rozšířena ze čtyř bitů na osm. Poté se čísla vynásobí a zahodí bity za osmý bit (jak ukazuje „ x “):

     00000110 (6)
 * 11111011 (−5)
 =============
          110
         1100
        00000
       110000
      1100 000
     11000000
    x 10 000 000
 + xx00000000
 =============
   xx11100010

To je velmi neefektivní; zdvojnásobením přesnosti předem musí být všechny přírůstky s dvojitou přesností a je zapotřebí alespoň dvakrát tolik dílčích produktů než pro efektivnější algoritmy skutečně implementované v počítačích. Některé multiplikační algoritmy jsou navrženy pro dvojkový doplněk, zejména Boothův multiplikační algoritmus . Metody pro násobení čísel znaménkové velikosti nefungují s čísly dvou doplňků bez přizpůsobení. Obvykle není problém, když je multiplicand (ten, který se opakovaně přidává k vytvoření produktu), záporný; problém je správně nastavit počáteční bity produktu, když je multiplikátor záporný. Běžné jsou dvě metody pro přizpůsobení algoritmů tak, aby zpracovávaly čísla dvou doplňků:

  • Nejprve zkontrolujte, zda je násobitel záporný. Pokud ano, před vynásobením negujte ( tj . Vezměte jejich doplněk) oba operandy. Násobitel pak bude kladný, takže algoritmus bude fungovat. Protože jsou oba operandy negovány, výsledek bude mít stále správné znaménko.
  • Odečtěte dílčí součin vyplývající z MSB (bit pseudo znaménka) místo jeho přidání jako ostatní dílčí součiny. Tato metoda vyžaduje, aby byl znaménkový bit multiplicandu prodloužen o jednu pozici, přičemž bude zachován během akcí posunu doprava.

Jako příklad druhé metody použijte běžný algoritmus sčítání a posuvu pro násobení. Namísto posouvání dílčích produktů doleva, jak se provádí tužkou a papírem, se nahromaděný produkt přesune doprava, do druhého registru, který nakonec pojme nejméně významnou polovinu produktu. Protože nejméně významné bity se po jejich výpočtu nezmění, přírůstky mohou mít jednoduchou přesnost a hromadí se v registru, který nakonec pojme nejvýznamnější polovinu produktu. V následujícím příkladu, opět vynásobením 6 x - 5, jsou dva registry a bit rozšířeného znaku odděleny "|":

  0 0110 (6) (multiplicand with extended sign bit)
  × 1011 (−5) (multiplikátor)
  = | ==== | ====
  0 | 0110 | 0000 (první dílčí součin (bit zcela vpravo je 1))
  0 | 0011 | 0000 (posun doprava, zachování rozšířeného znakového bitu)
  0 | 1001 | 0000 (přidat druhý dílčí součin (další bit je 1))
  0 | 0100 | 1000 (posun vpravo, zachování rozšířeného znakového bitu)
  0 | 0100 | 1000 (přidat třetí dílčí produkt: 0, takže žádná změna)
  0 | 0010 | 0100 (posun vpravo, zachování rozšířeného znakového bitu)
  1 | 1100 | 0100 (odečtěte poslední dílčí produkt, protože je ze znaménkového bitu)
  1 | 1110 | 0010 (posun doprava, zachování rozšířeného znakového bitu)
   | 1110 | 0010 (zahodit rozšířený znakový bit, konečná odpověď, −30)

Porovnání (objednání)

Porovnání je často implementováno s figurínou odčítání, kde jsou kontrolovány příznaky ve stavovém registru počítače , ale hlavní výsledek je ignorován. Zero flag indikuje, zda tyto dvě hodnoty v porovnání se rovnat. Pokud je příznak exclusive-or znaku a přetečení 1, výsledek odčítání byl menší než nula, v opačném případě byl výsledek nulový nebo větší. Tyto kontroly jsou často implementovány v počítačích v podmíněných větvích .

Binární čísla bez znaménka lze uspořádat jednoduchým lexikografickým uspořádáním , kde bitová hodnota 0 je definována jako menší než bitová hodnota 1. U hodnot komplementu dvou je význam nejvýznamnějšího bitu obrácen (tj. 1 je menší než 0).

Následující algoritmus (pro architekturu komplementu n -bitových dvou) nastaví registr výsledků R na −1, pokud A <B, na +1, pokud A> B, a na 0, pokud jsou A a B stejné:

// reversed comparison of the sign bit

if A(n-1) == 0 and B(n-1) == 1 then
    return +1
else if A(n-1) == 1 and B(n-1) == 0 then
    return -1
end
 
// comparison of remaining bits

for i = n-2...0 do
    if A(i) == 0 and B(i) == 1 then
        return -1
    else if A(i) == 1 and B(i) == 0 then
        return +1 
    end
end
 
return 0

Doplněk dvojky a 2adická čísla

V klasickém HAKMEM publikovaném laboratoří MIT AI v roce 1972 Bill Gosper poznamenal, že to, zda vnitřní reprezentace stroje je nebo není doplňkem dvou, lze určit součtem po sobě jdoucích sil dvou. Ve fantazii poznamenal, že výsledek tohoto postupu algebraicky naznačuje, že „algebra je spuštěna na stroji (vesmíru), který je dvojkovým doplňkem“.

Gosperův konečný závěr nemusí být nutně brán vážně a je podobný matematickému vtipu . Kritickým krokem je „... 110 = ... 111 - 1“, tj. „2 X = X  - 1“, a tedy X  = ... 111 = −1. To předpokládá metodu, pomocí které je nekonečný řetězec 1 s považován za číslo, což vyžaduje rozšíření konečných konceptů místo-hodnota v elementární aritmetice. Má smysl buď jako součást zápisu dvojkového doplňku pro všechna celá čísla, jako typické 2adické číslo , nebo dokonce jako jeden z generalizovaných součtů definovaných pro odlišnou řadu reálných čísel 1 + 2 + 4 + 8 + ·· · . Digitální aritmetické obvody, idealizované pro provoz s nekonečnými (rozšiřujícími se na kladné síly 2) bitových řetězců, vytvářejí 2adické sčítání a násobení kompatibilní se zastoupením dvou komplementů. Kontinuita binárních aritmetických a bitových operací v 2adické metrice má také určité využití v kryptografii.

Převod zlomků

Chcete -li převést číslo se zlomkovou částí, například .0101, je třeba převést počínaje zprava doleva na 1 s na desetinné místo jako při běžném převodu. V tomto případě se 0101 rovná 5 v desítkové soustavě. Každá číslice za plovoucí desetinnou čárkou představuje zlomek, kde jmenovatel je multiplikátor 2. Takže první je 1/2, druhá je 1/4 a tak dále. Když jsme již vypočítali desítkovou hodnotu, jak je uvedeno výše, použije se pouze jmenovatel LSB (LSB = začínající zprava). Konečný výsledek této konverze je 16/16.

Pokud má například plovoucí hodnota 0,0110, aby tato metoda fungovala, neměli byste uvažovat o poslední 0 zprava. Namísto výpočtu desítkové hodnoty pro 0110 tedy vypočítáme hodnotu 011, která je 3 v desítkové soustavě (ponecháním 0 na konci by byl výsledek 6, společně se jmenovatelem 2 4  = 16, což se zmenší na 3/8). Jmenovatel je 8, konečný výsledek je 3/8.

Viz také

Reference

Další čtení

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

externí odkazy