L`aritmetica in complemento a 2 (nozioni minime per passare l

L’aritmetica in complemento a 2
(nozioni minime per passare l’esame)∗
Mauro Brunato
Andrea Delai
Giovedı̀ 9 ottobre 2003
1
Qual è il problema?
Nell’usuale notazione intera in base 10, la necessità di rappresentare i numeri
relativi ci obbliga ad utilizzare un simbolo aggiuntivo, il segno “meno” (“−”)
per rappresentare numeri negativi, con la convenzione che se tale segno non è
presente il numero è da considerare positivo. La rappresentazione convenzionale
dei numeri relativi nel sistema decimale ci obbliga dunque a utilizzare undici
simboli diversi (in alternativa si aggiunge un dodicesimo segno, il “+”, che però
non è necessario).
Nell’aritmetica del calcolatore questo non è fattibile: il fatto di usare soltanto
due simboli (zero e uno) nelle rappresentazioni interne non è arbitrario, ma segue
necessariamente dalla struttura della macchina. Non è dunque possibile introdurre un simbolo ulteriore. I numeri, positivi o negativi, vanno rappresentati
come sequenze di cifre binarie di lunghezza prefissata.
2
Una prima soluzione
Ipotizziamo di lavorare con parole di otto bit, e di voler rappresentare il numero
3710 = 1001012. La disposizione dei bit nella parola sarà la seguente (sopra a
ogni bit è riportato il suo peso nella notazione posizionale):
27
0
26
0
25
1
24
0
23
0
22
1
21
0
20
1
Per rappresentare un numero negativo, una prima strada consiste nell’interpretare in modo speciale il bit più significativo, quello di peso 27 . Si può
assegnare a quel bit il significato di bit di segno: se vale 0, il numero è positivo;
se vale 1 il numero rappresentato è negativo. In tal caso, il numero −37 ha la
seguente rappresentazione:
±
1
26
0
25
1
24
0
23
0
∗ Il
22
1
21
0
20
1
sottotitolo è un chiaro esempio di terrorismo psicologico, come qualcuno ha detto a
lezione...
1
La differenza dal numero 37 è esclusivamente nel primo bit. Tale notazione,
pur semplice da capire, non è però adatta alle operazioni aritmetiche. Proviamo,
ad esempio, a calcolare l’operazione −37 + 1, il cui risultato — a detta degli
esperti — dovrebbe essere −36:
1
0
1
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
1
0
0
1
1
1
0
+
=
= −38
L’operazione di somma fornisce risultati sbagliati quando gli addendi hanno
segni diversi. Quando si esegue una somma, dunque, si dovrebbero verificare i
segni dei due numeri e, se risultano diversi, si dovrebbe eseguire una sottrazione.
Ciò costringe il calcolatore ad eseguire un’operazione di verifica in più prima
di eseguire l’addizione, proprio come accade quando la eseguiamo a mano nel
sistema decimale, aggiungendo complicazioni al codice eseguibile.
Un problema ulteriore di questa notazione è il fatto che lo zero ha due
rappresentazioni distinte, corrispondenti a +0 e a −0:
±
0
26
0
25
0
24
0
23
0
22
0
21
0
20
0
±
1
26
0
25
0
24
0
23
0
22
0
21
0
20
0
Ne risulta che due espressioni intere possono entrambe avere valore zero,
eppure essere diverse se confrontate tra loro, a meno di trattare a parte il caso
particolare, aggiungendo nuovamente complicazioni al codice da eseguire.
3
La soluzione “giusta”
Una soluzione migliore, che risolve entrambi i problemi citati in precedenza, è
la cosiddetta notazione in “complemento a due”. Essa consiste ancora nall’interpretare in modo arbitrario il significato del bit più significativo. A differenza dalla rappresentazione vista prima, però, l’interpretazione posizionale viene
mantenuta e si modifica soltanto il suo peso, invertendolo. Il bit più significativo
di una parola a otto bit pesa dunque −27 = −128. Consideriamo ad esempio il
seguente numero (che nella notazione precedente vale −37):
−27
1
26
0
25
1
24
0
23
0
22
1
21
0
20
1
In complemento a due, questa rappresentazione vale
−27 + 25 + 22 + 20 = −128 + 37 = −91.
In generale, siccome la somma di tutti i pesi positivi è
26 + 25 + · · · + 20 = 27 − 1,
tutti i pesi positivi presi insieme non arrivano a bilanciare il peso negativo. Ne
segue che lo zero ha una rappresentazione unica e che tutti i numeri che hanno
il bit più significativo uguale a 1 sono negativi (come prima).
2
Per stabilire la codifica di un generico numero negativo n < 0, dunque,
sapendo che necessariamente il bit più significativo va posto a 1, è sufficiente
riportare nei restanti bit il numero positivo che, sommato a −27 , dà il valore di
n. Per esempio, proviamo a codificare −37. Essendo un numero negativo, il bit
più significativo vale 1:
−27
1
26
?
25
?
24
?
23
?
22
?
21
?
20
?
Nella parte restante della tabella dovremo inserire quel numero che sommato
a −128 dà −37:
−128 + x = −37 ⇒ x = 128 − 37 = 91.
La codifica di 91 è 1011011 (esercizio!), che riportato nella tabella precedente
fornisce la codifica desiderata:
−27
1
4
4.1
26
1
25
0
24
1
23
1
22
0
21
1
20
1
Operazioni in complemento a due
Somma
La somma funziona sempre, senza il bisogno da considerare casi particolari,
a patto che il risultato possa essere contenuto nella parola di memoria. Ad
esempio, la somma tra un numero positivo e uno negativo genera il risultato
corretto. Consideriamo la somma −37 + 41:
1
1
1
0
0
1
1
0
0
1
0
1
0
1
1
0
0
1
1
0
1
0
0
1
1
1
0
0
1
1
0
+
=
=4
Si noti che la somma funziona, a patto di trascurare l’ultimo riporto. Dal
punto di vista della CPU questo non è un problema: il bit di riporto andrebbe
posto come nona cifra (come si fa nelle somme tradizionali in base dieci), e
quindi cade automaticamente “fuori” dal numero!
Ovviamente, l’aritmetica in complemento a due non pone al riparo dalle vere
situazioni di overflow. Il numero positivo più grande rappresentabile con otto
bit in complemento a due è 27 − 1 = 127 (la somma di tutti i pesi positivi).
Sommando 1 a 127 si ottiene −128 (verificare!).
4.2
Inversione
Se già si conosce la rappresentazione binaria di un numero positivo, invertirne il
segno è semplice. Supponiamo di conoscere la rappresentazione binaria di n > 0
(positivo, quindi il bit più significativo vale 0). La rappresentazione di −n avrà
il primo bit posto a 1, in quanto negativo, e come visto sopra la parte positiva
sarà quel numero x tale che −128 + x = −n. Spostando la costante, otteniamo
x = 128 − n. Scriviamo quest’ultima uguaglianza nel modo seguente:
x = (127 − n) + 1.
3
(1)
Il numero 127 è rappresentato, come sappiamo, da una sequenza di sette 1.
Sottrarre n (che essendo positivo e rappresentabile in complemento a due con
otto bit è minore di 127) da 127 equivale a invertire tutti i suoi bit. Ad esempio,
calcoliamo 127-37 su 7 bit:
1
0
1
1
1
0
1
0
1
1
0
1
1
1
0
1
0
1
1
1
0
−
=
= 90
In base alla (1), basta sommare 1 per trovare il valore corretto per la parte
positiva del numero. Sono dunque sufficienti due passaggi per trasformare la
rappresentazione binaria di n in quella di −n in complemento a due:
−27
0
26
0
25
1
24 23 22
0
0
1
⇓
Inversione dei bit (anche quello
⇓
−27 26 25 24 23 22
1
1
0
1
1
0
⇓
Incremento di 1
⇓
−27 26 25 24 23 22
1
1
0
1
1
0
21
0
20
1
del segno)
21
1
20
0
21
1
20
1
Il sistema funziona, ovviamente, anche per trasformare la rappresentazione
di un numero negativo in quella del suo inverso.
5
Generalizzazione
Tutto quello che è stato scritto per parole di 8 bit è banalmente generalizzabile
a lunghezze di parola diverse. Per parole di ` bit, il bit più significativo, che
nell’aritmetica senza segno varrebbe 2`−1 , vale −2`−1 . Gli altri pesi restano
invariati. Ne segue che, mentre nell’aritmetica senza segno gli interi rappresentabili vanno da 0 a 2` − 1, nell’aritmetica in complemento a due vanno da −2`−1
a 2`−1 − 1 (verificare).
In linguaggio C, tutti i tipi numerici interi (int, short, char) adottano,
in mancanza di indicazioni specifiche, l’aritmetica in complemento a due. Per
dichiarare una variabile senza segno (ossia in grado di contenere solo numeri
positivi, utilizzando anche il bit più significativo), è necessario premettere la
parola chiave unsigned al nome di tipo:
Tipo
Carattere con segno
Carattere senza segno
Intero corto con segno
Intero corto senza segno
Intero con segno
Intero senza segno
Dichiarazione
char
unsigned char
short
unsigned short
int
unsigned int
4
bit
8
8
16
16
32
32
valori
−128 . . . 127
0 . . . 255
−32768 . . . 32767
0 . . . 65535
−2147483648 . . . 2147483647
0 . . . 4294967295