Complemento a due

In informatica, Il complemento a due, o complemento alla base, è il metodo più diffuso per la rappresentazione dei numeri con segno. L'espressione complemento a due viene spesso usata impropriamente per indicare l'operazione di negazione (cambiamento di segno) nei computer che usano questo metodo. La sua enorme diffusione è data dal fatto che i circuiti di addizione e sottrazione non devono esaminare il segno di un numero rappresentato con questo sistema per determinare quale delle due operazioni sia necessaria, permettendo tecnologie più semplici e con maggiore precisione; si utilizza un solo circuito, il sommatore, sia per l'addizione che per la sottrazione.

Col complemento a due, il bit più significativo del numero ha peso negativo o positivo; da questo deriva che tutti i numeri che cominciano con un "1" sono numeri binari negativi, mentre tutti i numeri che cominciano con uno "0" sono numeri binari positivi.

Un numero binario positivo si può rendere negativo invertendone i bit e sommando 1 al valore risultante. Ciò è matematicamente giustificabile se osserviamo come si comporta la somma di un numero binario e del suo inverso: il risultato è una sequenza 111...111 2 {\textstyle 111...111{_{2}}} , che in complemento a 2 rappresenta -1. In simboli:

x + x ¯ = − 1 ⇒ x + x ¯ + 1 = 0 {\displaystyle x+{\overline {x}}=-1\quad \Rightarrow \quad x+{\overline {x}}+1=0}

⇒ x ¯ + 1 = − x . {\displaystyle \quad \Rightarrow \quad {\overline {x}}+1=-x.}

Allo stesso modo si può ottenere il valore assoluto di un numero binario negativo, ossia prendendo il complementare (invertendo il valore dei singoli bit) e aggiungendo 1 al numero binario risultante.

Un numero binario di n {\displaystyle n} cifre può rappresentare con questo metodo i numeri compresi fra − 2 ( n − 1 ) {\displaystyle -2^{(n-1)}} e 2 ( n − 1 ) − 1 {\displaystyle 2^{(n-1)}-1} .

Ad esempio, un numero binario di 8 cifre può rappresentare i numeri compresi tra -128 e +127.

Questo metodo consente di avere un'unica rappresentazione dello zero (quando tutti i bit sono zero, eliminando così la ridondanza dello zero che si verifica con la rappresentazione in segno e modulo), e di operare efficientemente addizione e sottrazione sempre avendo il primo bit a indicare il segno.

Infatti se il bit più significativo (il primo) è uguale a 1, il numero in complemento a due sarà negativo, mentre se questo è uguale a zero il numero sarà positivo, ecco un esempio:

0110   1100 = 108 ; {\displaystyle 0110\ 1100=108;}

1001   0100 = − 108. {\displaystyle 1001\ 0100=-108.}

Questo metodo di rappresentazione ha notevoli vantaggi, soprattutto per effettuare somme e differenze. Il complemento a due supera infatti gli svantaggi della rappresentazione a modulo e segno soprattutto in termini di complessità realizzativa dei circuiti sommatori.

Come è possibile notare, in complemento a due, il primo bit diventa automaticamente il bit del segno (come per la rappresentazione a modulo e segno), risolvendo però il problema dell'ambiguità dello 0 (in complemento a 2, 00000 {\displaystyle 00000} e 10000 {\displaystyle 10000} hanno significati diversi). Vengono inoltre enormemente facilitate le operazioni di somma e differenza, che si riducono alla sola operazione di somma. Per comprendere meglio è sufficiente un esempio:

5 10 − 10 10 = 5 10 + ( − 10 ) 10 = {\displaystyle 5_{10}-10_{10}=5_{10}+(-10)_{10}=}

= 0101 2 − 1010 2 = 00101 C A 2 + 10110 C A 2 = {\displaystyle =0101_{2}-1010_{2}=00101_{CA2}+10110_{CA2}=}

= 11011 C A 2 = − 0101 2 = − 5 10 . {\displaystyle =11011_{CA2}=-0101_{2}=-5_{10}.}

Per rappresentare l'opposto di un numero binario in complemento se ne invertono, o negano, i singoli bit: si applica cioè l'operazione logica NOT. Si aggiunge infine 1 al valore del numero trovato con questa operazione.

Ad esempio per rappresentare il numero -5 usando 8 bit in complemento a 2 il procedimento è il seguente:

Si parte dalla rappresentazione in binario del numero 5:

0000   0101. {\displaystyle 0000\ 0101.}

La prima cifra è 0, quindi il numero è sicuramente positivo. Si invertono tutti i bit: 0 diventa 1, e 1 diventa 0:

1111   1010. {\displaystyle 1111\ 1010.}

A questo punto si è ottenuto il complemento a uno del numero 5; per ottenere il complemento a due bisogna sommare 1 a questo numero:

1111   1010 + 0000   0001 = 1111   1011. {\displaystyle 1111\ 1010+0000\ 0001=1111\ 1011.}

Il risultato è un numero binario con segno che rappresenta il numero negativo -5 secondo il complemento a due. Il primo bit, avendo valore 1, evidenzia che il numero è negativo.

Il complemento a due di un numero negativo ne restituisce il numero positivo pari al valore assoluto: invertendo i bit della rappresentazione del numero -5 (sopra) si ottiene infatti:

0000   0100. {\displaystyle 0000\ 0100.}

Sommando 1 il risultato è:

0000   0100 + 0000   0001 = 0000   0101 {\displaystyle 0000\ 0100+0000\ 0001=0000\ 0101}

che è appunto la rappresentazione del numero +5 in forma binaria.

Si noti che il complemento a due dello zero è zero stesso: invertendone la rappresentazione si ottiene un byte di 8 bit pari a tutti 1, e aggiungendo 1 si ritorna a tutti 0 (l'overflow viene ignorato).

Operare l'addizione di due interi rappresentati con questo metodo non richiede processi speciali se essi sono di segno opposto, e il segno viene determinato automaticamente. Facciamo un esempio addizionando 15 e -5:

0 0 0 0 1 1 1 1 + 1 1 1 1 1 0 1 1 = 0 0 0 0 1 0 1 0 {\displaystyle {\begin{array}{r}0&0&0&0&1&1&1&1&+\\1&1&1&1&1&0&1&1&=\\\hline 0&0&0&0&1&0&1&0\end{array}}}

Questo processo gioca sulla lunghezza fissa di 8 bit della rappresentazione: viene ignorato un riporto di 1 che causerebbe un overflow, e rimane il risultato corretto dell'operazione (10).

Gli ultimi due bit (da destra a sinistra), ovvero i più significativi, della riga dei riporti contengono importanti informazioni sulla validità dell'operazione: se il risultato è compreso o non è compreso nell'intervallo dei numeri rappresentabili. Si verifica se il riporto è stato eseguito sul bit del segno ma non è stato portato fuori, o viceversa; più semplicemente, se i due bit più a sinistra sulla riga dei riporti non sono entrambi 0 o 1. Per verificare la validità del risultato è conveniente eseguire su questi due bit un'operazione XOR. Vediamo un esempio di addizione a 4 bit di 7 e 3:

0 1 1 1 + 0 0 1 1 = 1 0 1 0 {\displaystyle {\begin{array}{r}0&1&1&1&+\\0&0&1&1&=\\\hline 1&0&1&0\end{array}}}

In questo caso, come si può notare dal riporto presente solo sul bit più significativo, si è in presenza di overflow, per cui il risultato non è 10 (come sarebbe corretto) ma -6, infatti il massimo numero positivo rappresentabile in complemento a due su quattro bit è 7 (con n = 4 : 2 n − 1 − 1 = 7 {\displaystyle n=4:2^{n-1}-1=7} ).

Anche se la sottrazione potrebbe essere eseguita aggiungendo il complemento a due del sottraendo al minuendo, questo procedimento è poco utilizzato in quanto porta più complicazioni rispetto alla semplice costruzione di un circuito per la sottrazione. Come per l'addizione però, il vantaggio del complemento a due è l'eliminazione della necessità di esaminare i segni degli operandi per determinare quale operazione sia necessaria. Per esempio, sottrarre -5 a 15 è come aggiungere 5 a 15, ma questo è nascosto dal complemento a due:

0 0 0 0 1 1 1 1 − 1 1 1 1 1 0 1 1 = 0 0 0 1 0 1 0 0 {\displaystyle {\begin{array}{r}0&0&0&0&1&1&1&1&-\\1&1&1&1&1&0&1&1&=\\\hline 0&0&0&1&0&1&0&0\end{array}}}

L'overflow viene individuato con lo stesso metodo usato per l'addizione, esaminando i due bit più a sinistra sulla riga dei riporti: se sono differenti si è verificato un overflow.

Facciamo un altro esempio con una sottrazione con risultato negativo ( 15 − 35 = − 20 {\displaystyle 15-35=-20} ):

0 0 0 0 1 1 1 1 − 0 0 1 0 0 0 1 1 = 1 1 1 0 1 1 0 0 {\displaystyle {\begin{array}{r}0&0&0&0&1&1&1&1&-\\0&0&1&0&0&0&1&1&=\\\hline 1&1&1&0&1&1&0&0\end{array}}}

A parte una singola eccezione, cercando il complemento a due di ogni numero rappresentato con questo metodo, otteniamo il suo opposto: 5 diventa -5, 12 diventa -12, ecc.

Il minor numero rappresentabile (cioè quello negativo con maggior valore assoluto) costituisce l'unica eccezione: vediamo l'esempio del numero -128 nella rappresentazione a 8 bit:

1000   0000 {\displaystyle 1000\ 0000}

invertendo i bit si ottiene

0111   1111 {\displaystyle 0111\ 1111}

e aggiungendo 1 diventa

1000   0000. {\displaystyle 1000\ 0000.}

Questo perché 127 è il maggior numero con segno rappresentabile con 7 bit. Si noti che viene segnalato un overflow perché c'è un riporto sul bit del segno ma non fuori di esso.

Nonostante questo sia un numero unico, la sua rappresentazione è valida. Tutte le operazioni possono funzionare con esso sia come operando che come risultato (a meno che non sia successo un overflow).

I 2 n {\displaystyle 2^{n}} possibili valori degli n {\displaystyle n} bit che vanno a costituire la rappresentazione di un numero intero in forma binaria formano un anello di classi d'equivalenza, ovvero gli interi (modulo 2 n {\displaystyle 2^{n}} ). Ciascuna classe rappresenta un insieme

{ j + k ⋅ 2 n ∣ k ∈ Z } , ∀ j ∈ Z , 0 ≤ j ≤ 2 n − 1. {\displaystyle \{j+k\cdot 2^{n}\mid k\in \mathbb {Z} \},\qquad \forall j\in \mathbb {Z} ,\,\,0\leq j\leq 2^{n}-1.}

Esistono 2 n {\displaystyle 2^{n}} insiemi del genere, e l'addizione e la moltiplicazione sono ben definite all'interno di essi.

Se le classi sono impiegate per rappresentare i numeri tra 0 e 2 n − 1 {\displaystyle 2^{n}-1} , e l'overflow viene ignorato, si ha un insieme di interi senza segno; ma ognuno di essi è equivalente a sé stesso meno 2 n {\displaystyle 2^{n}} . Quindi le classi possono essere intese come la rappresentazione dei numeri tra − 2 n − 1 {\displaystyle -2^{n-1}} e 2 n − 1 − 1 {\displaystyle 2^{n-1}-1} , sottraendo 2 n {\displaystyle 2^{n}} dalla metà di essi.

Per semplicità: con 8 bit si possono rappresentare i numeri interi da 0 a 255. Sottraendo 256 alla metà superiore (da 128 a 255) si ottengono i numeri da -128 a -1, e l'insieme totale comprende ora i numeri da -128 a 127, con segno.

La relazione col complemento a due è resa evidente dal fatto che 256 = 255 + 1, e che 255 − x {\displaystyle 255-x} è il complemento a uno di x . {\displaystyle x.}

Esempio

-95 modulo 256 equivale a 161, dal momento che:

− 95 + 256 = − 95 + 255 + 1 = 255 − 95 + 1 = 160 + 1 = 161 {\displaystyle {\begin{aligned}-95+256&=-95+255+1\\&=255-95+1\\&=160+1\\&=161\end{aligned}}}

1 1 1 1 1 1 1 1 − 0 1 0 1 1 1 1 1 = 1 1 1 0 1 1 0 0 + 1 = 1 0 1 0 0 0 0 1 {\displaystyle {\begin{array}{r}1&1&1&1&1&1&1&1&-\\0&1&0&1&1&1&1&1&=\\\hline 1&1&1&0&1&1&0&0&+\\&&&&&&&1&=\\\hline 1&0&1&0&0&0&0&1\end{array}}}

255 − 95 = 160 + 1 = 161 {\displaystyle {\begin{array}{r}&255&-\\&95&=\\\hline &160&+\\&1&=\\\hline &161\end{array}}}

• David A. Patterson, John L. Hennessy e Perry Alexander, Computer organization and design: the hardware/software interface, 5. ed, Elsevier Morgan Kaufmann, 2014, ISBN 978-0-12-407726-3.

• Algoritmo di Booth
• Grandezza e segno
• Complemento a uno
• Eccesso N

• complemento a due, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Denis Howe, twos complement, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL