One's complement

One's complement of 1-complement is een van de twee getalsrepresentaties voor gehele getallen (integers) die in computers algemeen in omloop zijn (het andere systeem is two's complement (2-complement).

Positieve getallen worden in dit systeem voorgesteld door een bitrij beginnend met een 0 en verder door de gebruikelijke binaire voorstelling. Negatieve getallen beginnen met een 1 en het tegengestelde van een getal bestaat uit de bitrij met alle bits geïnverteerd, dus de rij met complementaire bits. Het positieve getal 79 bijvoorbeeld wordt (met 8 bits) voorgesteld door 01001111 en −79 door de rij complementaire bits 10110000. Men kan de voorstelling van −79 ook verkrijgen door de bitrij die 79 voorstelt, af te trekken van de rij met alleen enen: 11111111. Hiervan komt de naam: 1-complement. Als gevolg van deze representatie zijn er twee bitrijen die de waarde 0 voorstellen, nl. 00000000 en 11111111.

Formeel beschreven betekent 1-complement, dat de bitrij $b_{n}b_{n-1}\cdots b_{0}$ een positief getal voorstelt als de bit $b_{n}=0$ en een negatief getal als $b_{n}=1$. Het positieve getal $0b_{n-1}\cdots b_{0}$ stelt het binair geschreven getal N voor, en het tegengestelde hiervan, −N, wordt voorgesteld door de bitrij $1{\overline {b_{n-1}\cdots b_{0}}}$, waarin alle bits geïnverteerd zijn. De som van beide levert de bitrij 111...1 op, die dus ook het getal 0 voorstelt.

Anders gezegd: vermenigvuldiging van een bitrij met −1 in 1-complement komt overeen met het vervangen van iedere 0 door een 1 en iedere 1 door een 0, het uitvoeren van de booleaanse operator NOT (zie ook NOT-poort).

Het gebruik van 1-complement heeft enige gevolgen voor het uitvoeren van rekenkundige operaties (zie hiervoor Integer (informatica)).

Geschiedenis

Een van de belangrijke discussies in de begintijd van de digitale computers ging over de voorstelling van negatieve getallen. Onder de verschillende opvattingen van de experts was ook het tegenwoordig meest gebruikte two's-complement. Andere opvattingen waren het systeem van one's-complement en het systeem van "teken-en-grootte" (sign-magnitude) waarin tegengestelde getallen eenvoudigweg complementaire tekenbits hebben.

Elk van de systemen had voor- en nadelen. One's-complement maakte eenvoudiger hardware mogelijk, omdat er geen conversie nodig was bij uitwisseling van waarden met de rekeneenheid en was het gemakkelijk de tegengestelde van een getal te bepalen door eenvoudig alle bits te inverteren. Maar het stond veel wiskundigen tegen, dat er ook een negatieve 0 (−0) bestond, die zich net zo gedroeg als de positieve 0. Bovendien kan bij one's-complement een soort overflow optreden waardoor de logica voor optellen en aftrekken complexer wordt. Computers uit de CDC 6000-serie en de Univac 1100-serie maakten gebruik van one's-complement. Two's complement is het gemakkelijkst te implementeren in de hardware, waaraan het waarschijnlijk zijn populariteit te danken heeft. De processor in de vroege mainframes bevatten duizenden losse transistors, zodat het kostenbesparend was daarop te bezuinigen. De ontwerpers van de vroegste met geïntegreerde schakelingen (IC's) uitgeruste CPU's kozen voor two's complement. Met het voortschrijden van de IC-technologie werd dit systeem bijna door iedereen gevolgd, zoals door Intel, AMD en IBM.