Complemento a due
Il complemento a due (in inglese Two's complement) è il metodo più diffuso per la rappresentazione dei numeri negativi in informatica. Il termine Complemento a due viene spesso usato (erroneamente) 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 maggiore precisione; si utilizza un solo circuito (l'addizionatore) sia per l'addizione che per la sottrazione.
Col complemento a due, il bit iniziale (più a sinistra) 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 e se ne ottiene il valore assoluto complementando (invertendo) il valore dei singoli bit e aggiungendo 1 al numero binario risultante.
Un numero binario di n cifre può rappresentare con questo metodo i numeri compresi fra -2n-1 e +2n-1-1, così un binario di 8 cifre può rappresentare i numeri compresi tra -128 e +127.
Da notare che esiste una sola rappresentazione dello zero: quando tutti i bit sono zero, eliminando così la ridondanza dello zero che si verifica con la rappresentazione in modulo e segno.
Questo metodo consente di avere un'unica rappresentazione dello zero, e di operare efficientemente addizione e sottrazione sempre avendo il primo bit a indicare il segno.
Calcolo dell'inverso in complemento a due
Per rappresentare l'inverso di un numero binario in complemento a due di un numero binario 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.
Facciamo un esempio rappresentando il numero -5 con 8 bit in complemento a 2:
0000 0101 (5)
Partiamo dalla rappresentazione in binario del numero 5. La prima cifra è 0, quindi il numero è sicuramente positivo. Invertiamo i bit: 0 diventa 1, e 1 diventa 0:
1111 1010
A questo punto abbiamo ottenuto il complemento a uno del numero 5; per ottenere il complemento a due aggiungiamo 1 a questo numero:
1111 1011 (-5)
Il risultato è un numero binario con segno che rappresenta il numero negativo -5 secondo il complemento a due. Il primo bit, pari a 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) otteniamo:
0000 0100
Aggiungendo 1 otteniamo:
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 1, e aggiungendo 1 si ritorna a tutti 0 (l'overflow viene ignorato).
Addizione
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:
11111 111 (riporto) 0000 1111 (15) + 1111 1011 (-5) =========== 0000 1010 (10)
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à del risultato: se questo è compreso nell'insieme di numeri rappresentabili con questo sistema o è accaduto un overflow. Questo si è verificato se un 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 EXOR. Vediamo un esempio di addizione a 4 bit di 7 e 3:
0111 (riporto) 0111 (7) + 0011 (3) ============= 1010 (−6) Il risultato non è valido!
Sottrazione
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 che semplicemente costruire un circuito per la sottrazione. Ma come per l'addizione, 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:
11110 000 (riporto) 0000 1111 (15) − 1111 1011 (−5) =========== 0001 0100 (20)
L'overflow viene individuato con lo stesso metodo usato per l'addizione, esaminando i 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:
11100 000 (riporto) 0000 1111 (15) − 0010 0011 (35) =========== 1110 1100 (−20)
Particolarità
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 (−128) 0111 1111 (bit invertiti) 1000 0000 (aggiunto 1)
Questo perché 127 è il maggior numero con segno rappresentabile con 8 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).
Analisi matematica
I 2n possibili valori degli n bit che vanno a costituire la rappresentazione di un numero intero in forma binaria formano un anello di classi di equivalenza, ovvero gli interi (modulo 2n). Ciascuna classe rappresenta un insieme {j + k·2n | k è un intero} per ogni intero j, 0 ≤ j ≤ 2n − 1. Esistono 2n 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 2n − 1, e l'overflow viene ignorato, si ha un insieme di interi senza segno; ma ognuno di essi è equivalente a sé stesso meno 2n. Quindi le classi possono essere intese come la rappresentazione dei numeri tra −2n−1 e 2n−1 − 1, sottraendo 2n 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 è il complemento a uno di x.
Esempio
-95 modulo 256 equivale a 161, dal momento che:
- −95 + 256
- = −95 + 255 + 1
- = 255 − 95 + 1
- = 160 + 1
- = 161
1111 1111 255 − 0101 1111 − 95 =========== ===== 1010 0000 (complemento a uno) 160 + 1 + 1 =========== ===== 1010 0001 (complemento a due) 161