Two's complement

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
teken- bit
0 1 1 1 1 1 1 1 = 127
0 0 0 0 0 0 1 0 = 2
0 0 0 0 0 0 0 1 = 1
0 0 0 0 0 0 0 0 = 0
1 1 1 1 1 1 1 1 = −1
1 1 1 1 1 1 1 0 = −2
1 0 0 0 0 0 0 1 = −127
1 0 0 0 0 0 0 0 = −128

Waarden voor een 8-bitsgetal

Two's complement of 2-complement is een getalsrepresentatie voor gehele getallen (integers) die in computers algemeen wordt gebruikt.

Het is niet alleen associatief, maar heeft maar één representatie voor '0', de voor de hand liggende. Het 2-complement is gelijk aan het 1-complement plus 1 als de tekenbit '1' is, dus bij negatieve getallen.

Positieve getallen worden ook hierin voorgesteld door een bitrij beginnend met een 0 en negatieve beginnend met een 1, maar het tegengestelde bestaat nu uit een bitrij die verkregen wordt als het verschil met de bitrij met allemaal 0-en en een 1 als extra bit ervoor geplaatst. Deze bitrij stelt dan het getal 2n voor bij een representatie met n bits. De representatie komt neer op het rekenen modulo 2n. Het positieve getal 79 bijvoorbeeld wordt (met 8 bits) voorgesteld door 01001111 en -79 door 10110001. Tellen we beide op, dan krijgen we als som de rij 100000000, die overigens zelf in de representatie niet voorkomt.

Uit het bovenstaande kan afgeleid worden dat de representatie in 2-complement verkregen wordt door bij de representatie in 1-complement 1 op te tellen: -79 in 1-complement (8 bits) 10110000; tel er 1 bij op: 10110000 + 00000001 = 10110001, de voorstelling van -79 in 2-complement.

Net als bij 1-complement wordt bij 2-complement de meest significante bit gebruikt om aan te geven of een getal positief is of negatief. Deze meest significante bit heeft echter een andere betekenis dan bij 1-complement: in plaats van de rol van een soort minteken te vervullen, staat de meest significante bit (zeg, bit nummer n) voor -1 * 2^{n-1}. De rest van de bits wordt "normaal" geïnterpreteerd en een negatief getal wordt dan ook gevormd door de positieve waarde van de minder significante bits op te tellen bij -1 * 2^{n-1}.

Door deze definitie van getallen is de hoogste waarde die gerepresenteerd kan worden met een bitrij waarvan de meest significante bit de waarde 1 heeft, de waarde -1. In tegenstelling tot 1-complement is er dus niet zoiets als -0 in 2-complement notatie. Bijgevolg is het aantal representeerbare negatieve waarden in 2-complement ook 1 groter dan het aantal representeerbare positieve waarden: van -1 * 2^{n-1} tot en met 2^{n-1} -1.

De relatie tussen positieve en negatieve waarden is dan ook als volgt:

Zij b = 0b_{n-1} \cdots b_{0} een bitrij die de waarde N representeert. Dan is (met dezelfde definitie voor complement van een bit als bij 1-complement) de bitrij die -N representeert gelijk aan 1b_{n-1}^* \cdots b_{0}^* + 1.

Het idee is als volgt: stel dat met een bitrij de waarden -1 * 2^{n} + 1 tot en met 2^{n} -1 zou kunnen worden gerepresenteerd in 2-complement notatie (dus dan zou de interpretatie van de meest significante bit -1 * 2^{n} + 1 zijn in plaats van -1 * 2^{n}). Voor iedere representeerbare negatieve waarde -N geldt dan: -N = (-1 * 2^{n} + 1) + (2^{n} -1 - N). Gegeven een waarde N, vinden we de waarde (2^n -1 - N) door van alle bits behalve de meest significante het complement te nemen. Tellen we deze waarde op bij -1 * 2^{n} + 1 (door ook de meest significante bit 1 te maken), dan vinden we (-1 * 2^{n} + 1) + (2^{n} -1 - N) = -N. Echter, we hadden afgesproken dat de waarde van de meest significante bit -1 * 2^{n} is en niet -1 * 2^{n} + 1. Om die ontbrekende 1 te compenseren, moet er 1 bij de complement-notatie opgeteld worden om bij N de waarde -N te vinden.

Als voorbeeld vinden we -77 uit 77 in 2-complement als volgt:

   77 = 010011012      
  ---------------- not               alles inverteren (is not)
  -78 = 101100102         
    1 = 000000012         1 erbij optellen (is inc)
  ---------------- +
  -77 = 101100112         en we hebben het 2-complement

Een andere uitleg is:

   77 = 010011012      
   77*= 001100102 = 50    alles inverteren behalve het tekenbit
 
 -128 = 100000002         het tekenbit inverteren
   50 = 001100102         optellen bij het geïnverteerde getal
 ---------------- +
  -78 = 101100102         nu zijn alle bits geïnverteerd
    1 = 000000012         1 erbij optellen
 ---------------- +
  -77 = 101100112         en we hebben het 2-complement

Dus in het kort is 2-complement gelijk aan 1-complement (inverteer alle bits) met daarbij 1 opgeteld. De 2-complement representatie van een integer is vooral zinvol in verband met het optellen van getallen in hardware. Als 2-complement gebruikt wordt, maakt het niet uit of een of beide operanden negatief zijn. Hierdoor is een optelschakeling op een computerchip eenvoudiger te implementeren dan voor andere representaties. Een aparte schakeling om een getal van een ander getal af te trekken, hoeft niet te worden gemaakt. In dat geval wordt een van de operanden negatief gemaakt alvorens deze op te tellen.