One's complement

One's complement of 1-complement is een getalsrepresentatie voor gehele getallen (integers) die in computers gebruikt wordt. Een ander systeem, dat tegenwoordig het meest gebruikt wordt, 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}\ldots b_{1}$ een positief getal voorstelt als de bit $b_{n}=0$ en een negatief getal als $b_{n}=1$. Het positieve getal $0b_{n-1}\ldots b_{1}$ stelt het binair geschreven getal $N$ voor, en het tegengestelde hiervan, $-N$, wordt voorgesteld door de bitrij $1{\overline {b_{n-1}\ldots b_{1}}}$, 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).

Rekenoperaties

Rekenen in one's complement, d.w.z optellen, aftrekken en vermenigvuldigen, gaat op de gebruikelijke manier, zij het met enkele geringe aanpassingen. Natuurlijk met de normale beperking van het aantal bits. Aan de hand van enkele voorbeelden in 8 bits zal een en ander gedemonstreerd worden.

Optellen

Bereken 19 + 7:

   0001 0011          19
   0000 0111           7
  —————————— +       ———
   0001 1010          26

Bereken 19 + (−7):

   0001 0011          19
   1111 1000          −7
  —————————— +       ———
(1)0000 1011          11 + (1) De overflow moet bij het resultaat opgeteld worden.

Bereken −19 + 7:

   1110 1100         −19
   0000 0111           7
  —————————— +       ———
   1111 0011         −12

Bereken −19 + (−7):

   1110 1100         −19
   1111 1000          −7
  —————————— +       ———
(1)1110 0100         −27 + (1)

Aftrekken

Bereken 19 − 7:

       0001 0011          19
       0000 0111           7
      —————————— −       ———
       0000 1100          12

Bereken 19 − (−7):

       0001 0011          19
       1111 1000          −7
      —————————— −       ———
   (−1)0001 1011          27 + (−1)

Bereken −19 − 7:

       1110 1100         −19
       0000 0111           7
      —————————— −       ———
       1110 0101         −26

Bereken −19 − (−7):

       1110 1100         −19
       1111 1000          −7
      —————————— −       ———
   (−1)1111 0100         −11 + (−1)

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, de Electrologica-computers 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 processoren 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.