Jeden doplněk - Ones' complement
| Bity | Nepodepsaná hodnota |
Ones' doplňkem hodnota |
|---|---|---|
| 0111 1111 | 127 | 127 |
| 0111 1110 | 126 | 126 |
| 0000 0010 | 2 | 2 |
| 0000 0001 | 1 | 1 |
| 0000 0000 | 0 | 0 |
| 1111 1111 | 255 | −0 |
| 1111 1110 | 254 | -1 |
| 1111 1101 | 253 | -2 |
| 1 000 0001 | 129 | -126 |
| 1000 0000 | 128 | -127 |
The jedničkový doplněk z binární číslo je hodnota získaná obrácením všechny bity v binární reprezentaci čísla (swapping 0 a 1). Tato matematická operace je primárně zajímavá v informatice , kde má různé účinky v závislosti na tom, jak konkrétní počítač představuje čísla.
Nechybí ty komplementový systém , nebo ty doplňkem aritmetický je systém, ve kterém jsou záporná čísla reprezentována inverzní binárních reprezentací jejich odpovídajícími kladná čísla. V takovém systému je číslo negováno (převedeno z pozitivního na negativní nebo naopak) výpočtem jeho komplementu. Systém číselných doplňků N-bitových jednotek může představovat pouze celá čísla v rozsahu - (2 N − 1 −1) až 2 N − 1 −1, zatímco dvojkový doplněk může vyjádřit −2 N − 1 až 2 N − 1 −1. Je to jedna ze tří společných reprezentací záporných celých čísel v mikroprocesorech spolu s dvojkovým doplňkem a znaménkovou velikostí .
Systém binárních číslic doplňku jedniček je charakterizován bitovým doplňkem jakékoli celočíselné hodnoty, který je aritmetickým záporem hodnoty. To znamená, že převrácení všech bitů čísla (logický doplněk) vytvoří stejný výsledek jako odečtení hodnoty od 0.
Mnoho počátečních počítačů, včetně UNIVAC 1101 , CDC 160 , CDC 6600 , LINC , PDP-1 a UNIVAC 1107 , používalo aritmetiku komplementu. Nástupci modelu CDC 6600 pokračovali v používání aritmetiky komplementárních doplňků až do konce 80. let a potomci UNIVAC 1107 ( řada UNIVAC 1100/2200 ) stále používají, ale většina moderních počítačů používá dvojkový doplněk .
Číselné vyjádření
Kladná čísla jsou stejný jednoduchý binární systém, který používá dvojkový doplněk a velikost znaménka. Záporné hodnoty jsou bitovým doplňkem odpovídající kladné hodnoty. Největší kladná hodnota je charakterizována tím, že bit znaménka (vyššího řádu) je vypnutý (0) a všechny ostatní bity jsou zapnuté (1). Nejnižší záporná hodnota je charakterizována tím, že bit znaménka je 1 a všechny ostatní bity jsou 0. Tabulka níže ukazuje všechny možné hodnoty ve 4bitovém systému od −7 do +7.
+ − 0 0000 1111 — Note that both +0 and −0 return TRUE when tested for zero 1 0001 1110 — and FALSE when tested for non-zero. 2 0010 1101 3 0011 1100 4 0100 1011 5 0101 1010 6 0110 1001 7 0111 1000
Základy
Přidání dvou hodnot je jednoduché. Jednoduše zarovnejte hodnoty na nejméně významném bitu a přidejte a šířte jakýkoli přenos na bit o jednu pozici vlevo. Pokud se přenášení prodlužuje za konec slova, říká se, že je „zabaleno kolem“, což je stav nazývaný „ přenášení konce “. Když k tomu dojde, bit musí být přidán zpět v bitu nejvíce vpravo. Tento jev se nevyskytuje v aritmetice komplementu dvou.
0001 0110 22 + 0000 0011 3 =========== ==== 0001 1001 25
Odečítání je podobné, až na to, že výpůjčky se spíše než nesou, jsou šířeny doleva. Pokud výpůjčka přesahuje konec slova, říká se, že je „zabaleno kolem“, podmínka zvaná „ výpůjčka na konci “. Když k tomu dojde, musí se bit odečíst od bitu nejvíce vpravo. Tento jev se nevyskytuje v aritmetice komplementu dvou.
0000 0110 6 − 0001 0011 19 =========== ==== 1 1111 0011 −12 —An end-around borrow is produced, and the sign bit of the intermediate result is 1. − 0000 0001 1 —Subtract the end-around borrow from the result. =========== ==== 1111 0010 −13 —The correct result (6 − 19 = -13)
Je snadné prokázat, že bitový doplněk kladné hodnoty je záporná velikost kladné hodnoty. Výpočet 19 + 3 vede ke stejnému výsledku jako 19 - (-3).
Přidejte 3 až 19.
0001 0011 19 + 0000 0011 3 =========== ==== 0001 0110 22
Odečtěte -3 od 19.
0001 0011 19 − 1111 1100 −3 =========== ==== 1 0001 0111 23 —An end-around borrow is produced. − 0000 0001 1 —Subtract the end-around borrow from the result. =========== ==== 0001 0110 22 —The correct result (19 − (−3) = 22).
Záporná nula
Záporná nula je podmínka, kde jsou všechny bity v podepsaném slově 1. Toto se řídí pravidly doplňku jedniček, že hodnota je záporná, když je bit nejvíce vlevo 1, a že záporné číslo je bitovým doplňkem velikosti čísla. Hodnota se při výpočtu chová také jako nula. Přidáním nebo odečtením záporné nuly do / od jiné hodnoty se vytvoří původní hodnota.
Přidání záporné nuly:
0001 0110 22 + 1111 1111 −0 =========== ==== 1 0001 0101 21 An end-around carry is produced. + 0000 0001 1 =========== ==== 0001 0110 22 The correct result (22 + (−0) = 22)
Odečtení záporné nuly:
0001 0110 22 − 1111 1111 −0 =========== ==== 1 0001 0111 23 An end-around borrow is produced. − 0000 0001 1 =========== ==== 0001 0110 22 The correct result (22 − (−0) = 22)
Záporná nula se snadno vytvoří v doplňku doplňku 1. Jednoduše přidejte kladné a záporné číslo stejné velikosti.
0001 0110 22 + 1110 1001 −22 =========== ==== 1111 1111 −0 Negative zero.
Ačkoli matematika vždy produkuje správné výsledky, vedlejším účinkem záporné nuly je, že software musí testovat zápornou nulu.
Vyhněte se záporné nule
Generování záporné nuly se nestane problémem, pokud je dosaženo sčítání s doplňujícím odečítačem. První operand je předán nemodifikovanému odčítání, druhý operand je doplněn a odčítání generuje správný výsledek, aby se zabránilo záporné nule. Předchozí příklad přidal 22 a −22 a vytvořil −0.
0001 0110 22 0001 0110 22 1110 1001 −22 1110 1001 −22 + 1110 1001 −22 − 0001 0110 22 + 0001 0110 22 − 1110 1001 −22 =========== ==== but =========== ==== likewise, =========== === but =========== === 1111 1111 −0 0000 0000 0 1111 1111 −0 0000 0000 0
„Rohové případy“ vznikají, když je jeden nebo oba operandy nula a / nebo záporná nula.
0001 0010 18 0001 0010 18
− 0000 0000 0 − 1111 1111 −0
=========== ==== =========== ====
0001 0010 18 1 0001 0011 19
− 0000 0001 1
=========== ====
0001 0010 18
Odečtení +0 je triviální (jak je uvedeno výše). Pokud je druhý operand záporná nula, je invertován a výsledkem je původní hodnota prvního operandu. Odečítání −0 je také triviální. Výsledkem může být pouze 1 ze dvou případů. V případě 1 je operand 1 −0, takže výsledek se vytvoří jednoduše odečtením 1 od 1 na každé bitové pozici. V případě 2 odečtení vygeneruje hodnotu, která je o 1 větší než operand 1, a koncovou výpůjčku . Dokončení výpůjčky generuje stejnou hodnotu jako operand 1.
Následující příklad ukazuje, co se stane, když jsou oba operandy plus nebo minus nula:
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0
+ 0000 0000 0 + 1111 1111 −0 + 0000 0000 0 + 1111 1111 −0
=========== ==== =========== ==== =========== ==== =========== ====
0000 0000 0 1111 1111 −0 1111 1111 −0 1 1111 1110 −1
+ 0000 0001 1
==================
1111 1111 −0
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0 − 1111 1111 −0 − 0000 0000 0 − 1111 1111 −0 − 0000 0000 0 =========== ==== =========== ==== =========== ==== =========== ==== 1 0000 0001 1 0000 0000 0 0000 0000 0 1111 1111 −0 − 0000 0001 1 =========== ==== 0000 0000 0
Tento příklad ukazuje, že ze 4 možných podmínek při přidání pouze ± 0 vytvoří sčítač −0 ve třech z nich. Doplňkový odečítač vyprodukuje −0, pouze když jsou oba operandy −0.
Viz také
Reference
- Donald Knuth : The Art of Computer Programming , Volume 2: Seminumerical Algorithms, kapitola 4.1