Aritmetica dei Calcolatori

Aritmetica dei Calcolatori
Luca Abeni
March 5, 2014
Codifica dei Numeri Interi
■
k bit → codificano 2k simboli/valori/numeri...
◆ Si usa la base 2 per codificare i numeri
◆ Numeri naturali n ∈ N : valori da 0 a 2k − 1
■
Come codificare numeri interi z ∈ Z?
◆ Problema: numeri negativi z < 0 ⇒ z ∈
/N
◆ Si codificano sempre 2k valori...
◆ ... Ma quali???
■
IEP1
Varie possibilit`a: modulo e segno, complemento a 1, complemento a 2,
...
Luca Abeni – 2 / 15
Codifica con Modulo e Segno
■
Idea semplice: si usano k − 1 bit per rappresentare il valore assoluto
(modulo) del numero...
■
...Ed un bit per codificare il segno!
◆ bit pi`
u significativo a 0: numero positivo
◆ bit pi`
u significativo a 1: numero negativo
■
Valori codificati: da −2k−1 + 1 a 2k−1 − 1
◆ 2k − 1 valori???
◆ Come mai??? Due diverse sequenze di bit per codificare lo 0? (+0
e −0???)
k−1
z
■
IEP1
}|
k−1
{
z
}|
{
1 000 . . . 0 vs 0 000 . . . 0
Luca Abeni – 3 / 15
Codifica in Complemento a 1
■
Altra idea semplice: i numeri negativi si rappresentano facendo il
complemento ad 1 del valore assoluto
◆ Numero positivo: rappresento il valore assoluto
◆ Numero negativo: cambio 0 in 1 e viceversa (complemento a 1 di
k
z }| {
x: 1 . . . 1 −x = (2k − 1) − x)
◆ Numeri positivi: ancora, bit pi`
u significativo a 0
k
z
IEP1
}|
k
{
z
}|
{
■
Ancora, due rappresentazioni dello 0 (+0 e −0)? 111 . . . 1 vs 000 . . . 0
■
Modulo e segno → Non facile da sommare...
■
Complemento a 1 → a volte le cose vanno meglio (se il bit pi`
u
significativo non da’ riporto, OK)
Luca Abeni – 4 / 15
Somma di Numeri in Complemento a 1
■
Algoritmo per sommare numeri interi codificati in complemento a 1:
1. Sommare le rappresentazioni dei due numeri
2. Se la somma del bit pi`
u significativo da’ riporto, sommarlo al
risultato
3. Se i riporti delle due cifre pi`
u significative della nuova somma sono
uguali, il risultato `e attendibile
4. Altrimenti, il risultato non `e rappresentabile su k bit
■
Esempio: 6 + −3 (codifica su 5 bit)
1
◆ 6 = 00110; −3 = 00011 = 11100
1
0
1
0
1
0
1
0
1
1
0
1
0
1
0
0
0
◆ 00010 + 1 = 00011 (= 3)
IEP1
Luca Abeni – 5 / 15
Complemento a 2
■
Complemento a 2 di un numero binario:
◆ Scorrere i bit a partire dalla destra
◆ Fino al primo bit che vale 1 (compreso), lasciare invariato
◆ A partire dal bit successivo, fare il complemento a 1
■
Equivalente a fare il complemento a 1 e poi sommare 1
k
z }| {
◆ Complemento in base 2 di x: 2k − x = 1 0 . . . 0 −x
■
Esempio: complemento in base 2 di 87 (= 10101112 )
◆ L’1 pi`
u a destra rimane invariato; inverto le altre cifre. 0101001
◆ 272 − 10101112 = 100000002 − 10101112 = 101001
◆ Complemento a 1 +1: 0101000 + 1 = 101001
IEP1
Luca Abeni – 6 / 15
Codifica in Complemento a 2
■
Numeri positivi: rappresentare il valore assoluto
■
Numeri negativi: rappresentati usando il complemento a 2 del valore
assoluto
◆ Ancora, il bit pi`
u significativo indica il segno
◆ Stavolta, la codifica dello 0 `
e unica
◆ Codifica i numeri da −2k−1 a 2k−1 − 1
■
E stavolta, la somma `e semplice...
◆ x + (−y) = x + (2k − y) = 2k + x − y...
◆ ...Su k bit, questo `
e equivalente a x − y
IEP1
Luca Abeni – 7 / 15
Esempi di Codifica
decimale
-4
-3
-2
-1
0
1
2
3
IEP1
modulo e segno
complemento a 1
111
110
101
100 / 000
001
010
011
100
101
110
111 / 000
001
010
011
complemento a 2
100
101
110
111
000
001
010
011
Luca Abeni – 8 / 15
Somme e Sottrazioni in Base 2
■
Come normalmente in base 10 (numeri in colonna, riporto, etc...)
■
Se si usa complemento a 2, funziona anche con numeri negativi
◆ Ma occhio agli overflow!!!
◆ Overflow? Numeri su k bit, ma risultato non rappresentabile su k
bit
◆ Matematica “dell’orologio”...
IEP1
0
0
0
1
0
0
1
1
0
1
0
1
1
0
0
0
0
1
0
1
■
Esempi: k = 6, 5 + 12
■
k = 7, 5 − 8; k = 7, −5 + 8; k = 7, −64 − 8; k = 7, 63 + 1;
Luca Abeni – 9 / 15
Esempi Senza Overflow
■
k = 7, 5 − 8
◆ 5 = 00001012 ; −8 = 00010002 + 12 = 11101112 + 12 = 11110002
0
1
1
0
1
1
0
1
1
0
1
1
1
0
1
0
0
0
1
0
1
◆ 11111012 =... −(11111012 + 12 ) = −00000112 = −3
■
k = 7, −5 + 8
◆ −5 = 00001012 + 1 = 11110102 + 12 = 1111011; 8 = 00010002
1
1 1 1
1 1 1
0 0 0
0 0 0
◆ 00000112 = 3
IEP1
0
1
1
0
0
0
0
0
0
1
0
1
0
1
0
1
Luca Abeni – 10 / 15
Esempio di Overflow
■
k = 7, −64 − 8
◆ 64 = 10000002 ;
−64 = 10000002 + 12 = 01111112 + 12 = 10000002
◆ 8 = 00010002 ; −8 = 00010002 + 12 = 11101112 + 12 = 11110002
1
1
1
0
0
1
1
0
1
1
0
1
1
0
0
0
0
0
0
0
0
0
◆ 01110002 = 56... WTH??? Sommando 2 numeri negativi si ottiene
un numero positivo???
■
−64 − 8 = −72...
◆ Posso rappresentare numeri fra −26 = −64 e 26 − 1 = 63...
◆ −72 non `
e rappresentabile!!!
IEP1
Luca Abeni – 11 / 15
Esempio di Overflow
■
k = 7, 63 + 1
◆ 63 = 01111112
◆ 1 = 000000012
1
0
0
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
◆ 10000002 = −(10000002 + 1) = −(01111112 + 12 ) = −1000000 =
−64... WTH??? Sommando 2 numeri positivi si ottiene un numero
negativo???
■
IEP1
Ancora, il risultato corretto (63 + 1 = 64) non sarebbe rappresentabile...
Luca Abeni – 12 / 15
Esempi ed Esercizi
■
Numeri su k = 7 bit, codificati in complemento a 2
■
Verificare se c’`e overflow
◆ 0110110 + 0000011
■
Somma di due numeri positivi: mi aspetto risultato positivo...
◆ 1001010 + 1111101
■
Somma di due numeri negativi: mi aspetto risultato negativo...
◆ 1001010 + 1100000
◆ 0100000 + 1111010
◆ 1100000 + 0000110
IEP1
Luca Abeni – 13 / 15
La Matematica dell’Orologio
■
Aritmetica modulare: considero solo n numeri interi
◆ Numeri da 0 a n − 1...
◆ ...O numeri da −n/2 a n/2 − 1...
■
Quando contando arrivo al numero pi`
u grande, riparto dal pi`
u piccolo
◆ Se i numeri vanno da 0 a n − 1, contando dopo (n − 1) + 1 = 0
(contando dopo n − 1 riparto da 0)
◆ Se i numeri vanno da −n/2 a n/2 − 1, contando dopo
n/2 − 1 + 1 = −n/2
` come se i numeri stessero sul quadrante di un orologio!
◆ E
■
Definizione pi`
u formale: si usano classi di congruenza modulo n
◆ Relazione di equivalenza fra due numeri: a ≡ b ⇔ a%n = b%n
IEP1
Luca Abeni – 14 / 15
Cosa Succede in Caso di Overflow?
■
Operazioni su numeri naturali rappresentati su k bit → aritmetica
modulo 2k
◆ Calcolando a + b si ottiene in realt`
a (a + b)%2k ...
◆ ...Se il risultato della somma `
e < 2k , allora (a + b)%2k = a + b ←
no overflow!
◆ Altrimenti, in risultato appare “strano”...
■
Usando rappresentazione in complemento a 2 dei numeri interi, il
discorso `e analogo:
◆ Se il risultato di una somma a + b `
e compreso fra −2k−1 e
2k−1 − 1, allora no overflow (risultato corretto)!
◆ Se il a + b < −2k−1 , ottengo a + b + 2k . Positivo!!! Overflow!
◆ Se il a + b > 2k−1 − 1, ottengo a + b − 2k . Negativo!! Overflow!
IEP1
Luca Abeni – 15 / 15

Download Report