Záporná čísla: dvojkový doplněk a ta jedna chybějící kladná
V bajtu je osm bitů a žádný z nich není „mínus“. Znaménko se musí někam vejít, a existují tři způsoby, jak to udělat. Dva se nepoužívají a stojí za to vědět proč.
| způsob | jak | proč se nepoužívá |
|---|---|---|
| přímý kód | nejvyšší bit je znaménko, zbytek velikost | dvě nuly (+0 a −0), a sčítačka musí porovnávat znaménka |
| jedničkový doplněk | záporné = všechny bity otočené | taky dvě nuly, a přenos se musí obtočit zpátky |
| dvojkový doplněk | otočit a přičíst jedničku | — |
Dvě nuly nejsou estetický problém. Znamenají, že if (x == 0) musí testovat dva
vzorky, a že jeden ze 256 stavů se plýtvá na duplikát.
- 0000 0101 = 5
Pět v osmi bitech. Nic zvláštního — váhy 4 a 1 jsou zapnuté.
- ~0000 0101 = 1111 1010
Jednobitová negace, NOT. Zatím to nic neznamená — je to jen opačný vzorek.
- 1111 1010 + 1 = 1111 1011
A tohle je celý trik. Nic víc v tom není.
- 0000 0101 + 1111 1011 = 10000 0000 → 0000 0000
Součet původního a nového vzorku je 256 — a 256 se do osmi bitů nevejde, takže z něj zbude nula. Přesně to, co se od −x čeká.
- a − b = a + (~b + 1)
Odčítání je sčítání s doplňkem. Procesor nemá zvlášť obvod na mínus — to je ta úspora, kvůli které tahle reprezentace vyhrála.
Ta asymetrie
Osmibitový rozsah se znaménkem je −128 až +127. Ne −127 až +127. Chybí jedna kladná hodnota, a důvod je banální: nula zabírá místo na kladné straně. Vzorků je 256, jeden padne na nulu, zbývá 255 na rozdělení mezi kladné a záporné — a lichý počet nejde rozdělit na půl.
Praktický důsledek, který kousne: −(−128)
je v osmi bitech pořád −128. Není kam to napsat. Otočíte bity, přičtete jedničku
a jste tam, kde jste byli. Kdo píše abs(x) nad osmibitovým vstupem, má tam jeden
případ, kdy výsledek vyjde záporný — a je to případ, který se v testech s náhodnými daty
objeví jednou z dvou set padesáti šesti.
Proč to vyhrálo
Protože procesor pak nepotřebuje odčítačku. Odečíst znamená přičíst doplněk, a přenos, který uteče přes horní hranu, se prostě zahodí:
To je úspora poloviny aritmetické jednotky výměnou za jedno pravidlo navíc. V roce 1949, kdy to poprvé postavil EDSAC, to bylo hodně; dnes je to zvyk, který se už nezmění.