Complemento a due

Da Wikipedia, l'enciclopedia libera.

Il complemento a due (in inglese two's complement) è il metodo più diffuso per la rappresentazione dei numeri con segno in informatica. 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 maggiore precisione; si utilizza un solo circuito, il sommatore, 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. Si può così ottenere il valore assoluto di un numero binario negativo, prendendo il complementare (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.

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 modulo e segno), e di operare efficientemente addizione e sottrazione sempre avendo il primo bit a indicare il segno.

Caratteristiche[modifica | modifica sorgente]

Questo metodo di rappresentazione ha notevoli vantaggi, soprattutto per effettuare somme e differenze: in pratica ai numeri viene anteposto un bit di valore zero; se poi il numero è negativo è necessario convertirlo in complemento a 2: per farlo è sufficiente leggere il numero da destra verso sinistra e invertire tutte le cifre a partire dal primo bit uguale a 1 (escluso). Per fare un esempio:

-12_{10} = -01100_2 = 10100_{CA2}

Come è possibile notare seguendo questo metodo il primo bit diventa automaticamente il bit del segno (come per il metodo precedente). Viene però risolto il problema dell'ambiguità dello 0 (in complemento a 2 00000 e 10000 hanno significati diversi) e vengono enormemente facilitate le operazioni di somma e differenza, che si riducono alla sola operazione di somma: per spiegare meglio basta fare un esempio:

5_{10} - 10_{10} = 5_{10} + (-10)_{10} = 0101_2 - 1010_2 = 00101_{CA2} + 10110_{CA2} = 11011_{CA2} = -00101_2 = -5_{10}

Calcolo dell'opposto in complemento a due[modifica | modifica sorgente]

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.

Facciamo un esempio rappresentando il numero -5 con 8 bit in complemento a 2.

Partiamo dalla rappresentazione in binario del numero 5:

0000 0101 (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 sommiamo 1 a questo numero:

1111 1010 + 0000 0001 = 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

Sommando 1 otteniamo:

0000 0100 + 0000 0001 = 0000 0101 (+5)

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[modifica | modifica sorgente]

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 1110  (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à 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:

 01110  (riporto)
  0111  (7)
+ 0011  (3)
=============
  1010  (-6)

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: 2n-1 - 1 = 7).

Sottrazione[modifica | modifica sorgente]

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:

  1111 0000  (riporto)
  0000 1111  (15)
− 1111 1011  (−5)
===========
  0001 0100  (20)

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:

  1110 0000  (riporto)
  0000 1111  (15)
− 0010 0011  (35)
===========
  1110 1100  (−20)

Particolarità[modifica | modifica sorgente]

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 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).

Analisi matematica[modifica | modifica sorgente]

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

Voci correlate[modifica | modifica sorgente]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica