Jeden doplněk

The něčí doplněk , i ( b -1) -complement , je aritmetický operace, která se většinou používá v duálním systému . Všechny číslice nebo bitů na binární čísla (binární číslo) jsou vedené, to znamená: 0to se stává off 1a vice versa. Výsledkem je, že každá číslice binárního čísla a její odpovídající číslice něčího doplňku se „ 1doplňují“, což dává operaci její název. Takže pokud -digit binární číslo, pak jeho něčí doplněk ${\ displaystyle z}$${\ displaystyle n}$

${\ displaystyle (2 ^ {n} \! - \! 1) -z,}$

odčítání , ve kterém nejsou žádné carry- do dalšího období . Operace je také známá jako bitová negace a operátor je v různých programovacích jazycích~ označován jako vlnovka . Číslo je interpretováno jako bitový řetězec .

Jednou aplikací vlastního doplňku je současná manipulace s jednotlivými bity v bitovém řetězci. Například pokud chcete Zahlsmazat všechny bity v bitovém řetězci, Maskekteré jsou nastaveny v bitovém řetězci , můžete ANDZahl s něčím doplňkem Maskebitově , v C syntaxiZahl &= ~Maske;

Další aplikací je reprezentace doplňku , technika pro binární reprezentaci záporných celých čísel . Dá se to snadno popsat - doplňkem reprezentace záporného čísla je normální binární vyjádření jeho množství - implementace aritmetické jednotky pro takto reprezentovaná čísla je však těžkopádná. Má pouze výhody oproti reprezentaci dvou doplňků , která je dnes běžná, v případě dělení, které je i tak obvykle pomalé, v násobení s dvakrát dlouhým výsledkem a ve vytváření jednoduchých kontrolních součtů .

Reprezentace doplňku

Binární kódování celých čísel se znaménkem má obvykle následující vlastnosti:

• řada konstanta n z číslic je použito ,
• nejvýznamnější bit indikuje znamení : 0za plus, 1za mínus,
• u kladných čísel souhlasí s nepodepsaným zastoupením, ve kterém jsou malá čísla vpředu doplněna nulami.

Když je nastaven nejvýznamnější bit, existují rozdíly. V tomto případě je částka získána vytvořením komplementu v reprezentaci komplementu. Například 1010úvodní se ukáže 1být záporný a částka je ~1010tedy 0101= 5. Tato definice má za následek následující další vlastnosti reprezentace doplňku:

• existují dvě reprezentace pro číslo 0, +0 = 0000a −0 = 1111,
• kladná a záporná čísla dosahují symetricky až do stejné výše, zde 7 = 0111.

Zde jsou uvedeny příklady pro délku slova n = 4 bity. Pro 8 a 16 bitů jsou maximální hodnoty obecně 127 a 32767${\ displaystyle 2 ^ {n-1} -1.}$

Aritmetické operace a problémy

Nejjednodušší aritmetickou operací v reprezentaci komplementu je aritmetická negace (unární -operátor). Je pouze nutné vytvořit bitový doplněk. To umožňuje odečítání (binární -operátor) zpětně sledovat přímo k sčítání: 3 - 4 = 3 + (−4). Chcete-li provést toto přidání, sčítač vytvořený pro nepodepsaná čísla dává správný výsledek:

           1011 (−4)
        +  0011 (+3)
Überträge 0011
          —————
        =  1110 (−1)

Nevýhodou reprezentace komplementu je řešení případu, kdy operace překročí nulu. Příklad: Při výpočtu −4 + ​​6 = +2 se po jednoduchém přidání binárního čísla reprezentací komplementu dvou lidí nejprve objeví nesprávný mezivýsledek:

 −4 + 6 = +2 führt zu
           1011
        +  0110
Überträge 1110
          —————
        =  0001 (Zwischenergebnis)

0001Kandidoval na +1, ne pro +2. Aby se zobrazil správný výsledek, musí se vyhodnotit přenos zleva (zde 1) a v případě potřeby se musí výsledek zvýšit o 1. Jinými slovy, přenos musí být přidán k mezivýsledku:

          0001 (Zwischenergebnis)
       +     1 (Übertrag der vorhergehenden Operation)
         —————
       =  0010

V prvním příkladu výše je přenos 0, takže mezivýsledek tam již odpovídá konečnému výsledku.

Další nevýhodou je vznik nadbytečnosti : Pro nulu existují dvě reprezentace: 0000(+0) a 1111(−0), viz znaménko nula . Na jedné straně se s omezeným počtem bitů nepoužívá maximální rozsah množství čísel, která lze reprezentovat. Rozsah čísel, který lze reprezentovat, je snížen o 1; protože nula je přítomna dvakrát, datové slovo pro rozsah čísel je vynecháno. Reprezentace všech ostatních čísel však zůstává jednoznačná. V tomto příkladu se 4 bity  je reprezentováno pouze 15 různých čísel (od -7 do 7) s 2 ⁴ = 16 různými bitovými kombinacemi.

Oběma popsaným problémům se při kódování čísel v reprezentaci komplementu těchto dvou předejde.

Přidání převoditelnosti zlepšuje citlivost jednoduchého kontrolního součtu vícenásobných bitových chyb. Například kontrolní součet s modulo aritmetickým ignorováním nese by neznamenal chybu přenosu s pravděpodobností 50%, pokud je často nejvýznamnější bit nesprávný, např. B. konstantní nula. TCP používá kontrolní součet v něčí doplňková aritmetika, který nemá tento nedostatek a jehož efektivní výpočet na hardware bez něčí doplňková aritmetickou jednotkou je popsána v RFC 1071 .

Zobecnění na b -adické systémy

V systému b -adic se standardní sadou číslic odpovídá binární inverze na číslici aritmetickému pravidlu . V desítkové soustavě s b = 10 musí být každá číslice odečtena od 9. Někteří autoři pak hovoří o komplementu devítky a obecně o komplementu ( b −1). Například devítkovým doplňkem je desetimístné desetinné číslo${\ displaystyle \ {0,1, \ ldots, b \! - \! \! 1 \}}$${\ displaystyle z}$${\ displaystyle {\ bar {z}} ~ = ~ (b \! - \! \! 1) -z}$456dez

${\ displaystyle {\ begin {aligned} {\ overline {456}} _ {\ mathrm {dec}} & = ((9-4) (9-5) (9-6)) _ {\ mathrm {dec} } \\ & = 543 _ {\ mathrm {dec}} \\ & = 999 _ {\ mathrm {dec}} -456 _ {\ mathrm {dec}}. \ End {zarovnáno}}}$

Takže pokud -digit číslo decimální, pak devíti doplňkem ${\ displaystyle x}$${\ displaystyle n}$

${\ displaystyle (10 ^ {n} \! - \! 1) -x,}$

odčítání , ve které nese nevyskytují.

webové odkazy

• John Walker : Minus Zero. Paměti UNIVAC - doplněk na počítačích UNIVAC 1100 (anglicky)

Individuální důkazy

1. ^ Helmut Herold: Základy informatiky . Pearson Studium, Mnichov 2007, ISBN 978-3-8273-7305-2 , s. 59
2. ^ Herbert Schneider-Obermann: Základní znalost elektrických, digitálních a informačních technologií . 1. vydání. Friedr. Vieweg & Sohn Verlag / GWV Fachverlage, Wiesbaden 2006, ISBN 978-3-528-03979-0 .  Tabulka 2.1: Záporná čísla v duálním systému v části 2.1.5 Zastoupení záporných čísel v duálním systému
3. ↑ RFC 1071: Výpočet internetového kontrolního součtu
4. ↑ Neunerkomplement atrechnerlexikon.de; Citováno 6. dubna 2015.