Esercitazioni su rappresentazione dei numeri e aritmetica dei calcolatori"

(1)

Esercitazioni su rappresentazione  dei numeri e aritmetica dei calcolatori"

slide a cura di Salvatore Orlando & Marta Simeoni "

(2)

Interi unsigned in base 2"

Si utilizza un alfabeto binario A = {0,1}, dove 0 corrisponde al numero zero, e 1 corrisponde al numero uno 

"d_n-1...d₁d₀ con di d_i∈ {0,1}"

Qual è il valore rappresentato ?"

Quanti e quali numeri sono rappresentabili su n bit?  

N = d_n-1• 2^n-1 + .... + d₁• 2¹ + d₀• 2⁰

Con sequenze di n bit sono rappresentabili 2ⁿ numeri naturali (da 0 a 2ⁿ-1)

00….00 = 0 00….01 = 1 00….10 = 2 …

01….11 = 2^n-1- 1 10….00 = 2^n-1 …

(3)

Interi unsigned in base 2"

I seguenti numeri naturali sono rappresentabili usando il numero di bit specificato ?"

20₁₀ su 5 bit ? "

64₁₀ su 6 bit ? "

500₁₀ su 9 bit ? "

1025₁₀ su 10 bit ? "

SI SI NO NO

Ricorda che:

2⁰ = 1 2¹ = 2 2² = 4 2³ = 8 2⁴ = 16 2⁵ = 32 2⁶ = 64 2⁷ = 128 2⁸ = 256 2⁹ = 512 2¹⁰ = 1024 ....

(4)

Conversione binario-decimale"

Esercizio: 1110101

₂

= ???

₁₀^"

1·2

⁶

+ 1·2

⁵

+ 1·2

⁴

+ 0·2

³

+ 1·2

²

+ 0·2

¹

+ 1·2

⁰

= 64 + 32 + 16 + 0 + 4 + 0 + 1

Soluzione: 1110101

²

= 117

¹⁰

(5)

Conversione decimale-binario"

Esercizio: 100

₁₀

= ???

₂^"

100 : 2 = 50 resto 0 50 : 2 = 25 resto 0 25 : 2 = 12 resto 1 12 : 2 = 6 resto 0

6 : 2 = 3 resto 0 3 : 2 = 1 resto 1 1 : 2 = 0 resto 1

Soluzione: 100

¹⁰

= 1100100

²

(6)

Conversione dec-bin: metodo più pratico

Scriviamo direttamente il numero decimale come somma di potenze di 2. Per far questo, sottraiamo via via le potenze di 2, a partire dalle più significative. "

Esercizio: 123

₁₀

= ???

₂

"

Ricorda che:

2⁰ = 1 2¹ = 2 2² = 4 2³ = 8 2⁴ = 16 2⁵ = 32 2⁶ = 64 2⁷ = 128 2⁸ = 256 2⁹ = 512

123 - 64 = 59 ==>

2⁶

59 - 32 = 27 ==>

2⁵

27 - 16 = 11 ==>

2⁴

11 - 8 = 3 ==>

2³

3 - 2 = 1 ==>

2¹

1 - 1 = 0 ==>

2⁰

Allora 123

₁₀

=

2⁶

+

2⁵

+ 2

⁴

+

2³

+

2¹

+

2⁰

(7)

Conversione binario-ottale e viceversa"

Esercizio: 10101111

₂

= ???

₈

"

Esercizio: 635

₈

= ???

₂

"

10 101 111

2 5 7

Soluzione: 10101111

²

= 257

⁸

6 3 5

110 011 101 Soluzione: 635

⁸

= 110011101

⁸

(8)

Base 16"

Quali dei seguenti numeri esadecimali sono numeri sono corretti?

^"

BED CAR 938 DEAD BEBE A129 ACI

DECADE BAG

DAD

4H3

(9)

Conversione binario-esadecimale e viceversa"

Esercizio: 101111101101₂ = ???_16"

Esercizio: A3C9₁₆ = ???_2"

Ricorda che:

1₁₀= 1₁₆ = 0001₂ 2₁₀= 2₁₆ = 0010₂ ...

9₁₀= 9₁₆ = 1001₂ 10₁₀= A₁₆ = 1010₂ 11₁₀= B₁₆ = 1011₂ 12₁₀= C₁₆ = 1100₂ 13₁₀= D₁₆ = 1101₂ 14₁₀= E₁₆ = 1110₂ 15₁₀= F₁₆ = 1111₂ 1011 1110 1101

B E D

A 3 C 9 1010 0011 1100 1001

Soluzione: 101111101101

²

= BED

¹⁶

= 3053

¹⁰

Soluzione: A3C9

¹⁶

= 1010001111001001

²

= 41929

¹⁰

(10)

Interi signed in complemento a 2"

Come si riconosce un numero positivo da uno negativo?"

–  Positivo ⇒ bit più significativo 0"

–  Negativo ⇒ bit più significativo 1"

Su n bit sono rappresentabili 2ⁿ interi unsigned (da 0 a 2ⁿ

-1

^)"

Sempre su n bit, quanti interi signed in complemento a 2 ?"

0...00 = 0 0...01 = 1 ...

01...11 = 2^n-1-1 (massimo pos.) 10...00 = -2^n-1 (minimo neg.) ...

11...11 = -1

in totale sempre

2

ⁿ

numeri

(11)

Interi signed in complemento a 2"

Dato N>0, il numero -N si rappresenta su n bit con il numero unsigned 2ⁿ - N

-1 ⇒ 2ⁿ - 1 (1...1) - 2^n-1⇒ 2ⁿ - 2^n-1 = 2^n-1 (10...0)

Data la rappresentazione di un numero negativo in complemento a due su n bit, il valore corrispondente si determina assegnando

- peso negativo al bit di segno (-2^n-1) - peso positivo a tutti gli altri bit

Esempio su 5 bit:

10011 = -2⁴ + 2¹ + 2⁰ = -13

(12)

Complemento a 2: cambio di segno"

Esercizio: Rappresentare -35₁₀ in complemento a 2 su 8 bit_"

00100011

₂

= +35

₁₀

11011100 + 1 = ---

11011101

Complemento a uno

Soluzione: -35

₁₀

= 11011101

₂

(13)

Complemento a 2: cambio di segno"

Esercizio: Rappresentare -35 in complemento a 2 su 8 bit_"

00100011

₂

= +35

₁₀

11011101

₂

Inverti (complementa a 1) tutti i bit a

sinistra del bit “1” meno significativo

(14)

Complemento a 2: cambio di segno"

Esercizio: Quale numero decimale rappresenta il seguente numero binario in complemento a due? "

1111 1111 1111 1111 1111 1110 0000 1100

₂

0000 0000 0000 0000 0000 0001 1111 0100

₂

= 2

²

+ 2

⁴

+ 2

⁵

+ 2

⁶

+ 2

⁷

+ 2

⁸

= 500

₁₀

Soluzione: il numero è -500

₁₀

(15)

Complemento a 2: somma e sottrazione"

Esercizio: eseguire 53₁₀ - 35₁₀ in complemento a due su 8 bit"

35

₁₀

= 00100011

₂

complementando: - 35

₁₀

= 11011101

₂

11111101

53

₁₀

- 53

₁₀

+ 00110101

₂

+ 35

₁₀

= (-35)

₁₀

=

11011101

₂

= ___ ⇒ _ ⇒____

18

₁₀

18

₁₀

(100010010

₂

) mod 2

⁸

00010010

₂

= 18

₁₀

(16)

Complemento a 2: somma e sottrazione"

Esercizio: eseguire 15₁₀ - 38₁₀ in complemento a due su 8 bit"

38

₁₀

= 00100110

₂

complementando: - 38

₁₀

= 11011010

₂

00011110

15

₁₀

- 15

₁₀

+ 00001111

₂

+ 38

₁₀

= (-38)

₁₀

=

11011010

₂

= ___ ⇒ _ ⇒____

-23

₁₀

-23

₁₀

(011101001

₂

) mod 2

⁸

00010111

₂

= 23

₁₀

(17)

Overflow"

In quali dei seguenti casi si può ottenere overflow?"

–  somma di due numeri con segno concorde? "

–  somma di due numeri con segno discorde? "

–  sottrazione di due numeri con segno concorde? "

–  sottrazione di due numeri con segno discorde? "

SI"

NO"

SI"

(18)

Come scoprire lʼoverflow"

Primo caso: "

somma algebrica di due numeri positivi A e B. Si ha overflow se A +B>=2^n-1, ovvero se A+B non può essere rappresentata su n bit in complemento a due."

Esempi:  

A=01111 B=00001 (OVERFLOW ⇒ due ultimi riporti discordi) 

A=01100 B=00001 (NON OVERFLOW ⇒ due ultimi riporti concordi) 

01 00

01111+ 01100+

00001= 00001=

10000 01101

(19)

Come scoprire lʼoverflow"

Secondo caso: "

somma algebrica di due numeri negativi A e B. Si ha overflow se |A|

+|B|>2ⁿ-1, ovvero se |A|+|B| non può essere rappresentata su n bit in complemento a due."

Esempi:

A=10100 B=10101 (OVERFLOW ⇒ due ultimi riporti discordi) 

A=10111 B=11101 (NON OVERFLOW ⇒ due ultimi riporti concordi)  

10 11

10100+ 10111+

10101= 11101=

01001 10100

(20)

Esercizio"

Considerate i numeri esadecimali x₁ = 7A x₂ = 13 x₃ = FF   x₄ = C1 x₅ = 84 "

Scrivere i cinque numeri in codice binario a 8 bit"

Interpretare il codice binario in complemento a due ed eseguire le operazioni  

x

₁

- x

₂

; x

₃

+ x

₄

; x

₄

+ x

₅

; x

₄

- x

₁

x₁ = 0111 1010 x₂ = 0001 0011 x₃ = 1111 1111 x₄ = 1100 0001 x₅ = 1000 0100

11111000 x₁ 01111010 +

-x 11101101 =

(21)

Esercizio (continua)"

11111111 x₃ 11111111 +

x₄ 11000001 = ___________

(111000000) mod 2⁸ = 11000000 overflow?

10000000 x₄ 11000001 +

x₅ 10000100 = ___________

(101000101) mod 2⁸ = 01000101 overflow?

10000000 x₄ 11000001 + -x₁ 10000110 = ___________

(101000111) mod 2⁸ = 01000111 overflow?

(22)

Esercizio - caso particolare"

Si ricorda che lʼopposto del numero negativo più piccolo su n bit non può essere rappresentato in complemento a due"

–  codifica non simmetrica"

Supponiamo quindi:"

–  di lavorare con rappresentazioni in complemento a due su 3 bit"

–  di dover effettuare la sottrazione x-y"

dove y=100₂ è il minimo numero rappresentabile (y=-4₁₀)"

Esercizio: calcolare x-y usando il solito algoritmo, dove x=001₂"

000 "

X 001 +"

-Y 100 "

______"

(0101) mod 2³ = 101 OVERFLOW, anche se "

Il complemento a due non ha effetto

(23)

Esercizio - caso particolare (continua)"

Esercizio

: calcolare

x-y

^{, dove}

x=111

_{2 "}

–  poiché

x=111

₂allora x = -1_10"

–  non dovremmo avere overflow, poiché vogliamo effettuare la somma algebrica di due numeri con segno discorde"

–  il risultato da ottenere è

x-y=-1

₁₀

- (-4

₁₀

) = 3

₁₀_"

100 "

X 111 +"

-Y 100 "

______"

(1011) mod 2³ = 011 = 3₁₀ NO OVERFLOW , anche"

" " " " " se riporti discordi !!"

Abbiamo infatti sottratto un numero negativo da un numero negativo ⇒ in questo caso non si può verificare overflow"

corretto

Il complemento a due non ha effetto

(24)

Procedura generale per determinare lʼOVERFLOW"

Operazione Segno 1

^o

operando

Segno 2

^o

operando

Segno atteso Somma

Somma Somma Somma

+ + -

- -

+

- qualsiasi qualsiasi

-

+ +

Sottrazione Sottrazione Sottrazione

+ +

- +

-

+ qualsiasi

Solo in questi"

casi si può "

verificare un "

OVERFLOW."

Possiamo "

controllarlo"

confrontando"

il bit di segno del "

risultato con il "

segno atteso."

Alla luce dellʼesempio precedente, guardare solo ai due ultimi riporti per controllare lʼOVERFLOW potrebbe quindi portare a risultati erronei"

(25)

Numeri con la virgola (virgola fissa)"

Data una base B, si assegnano: "

n cifre per rappresentare la parte intera"

m cifre per rappresentare la parte frazionaria"

In base B=2, abbiamo quindi m+n bit per parte intera e frazionazia"

m n"

Esempio:"

d

_n-1

...d

₁

d

₀

. d

_-1

...d

_-m

Qual è il numero rappresentato in base B?"

N = d

_n-1

• B

^n-1

+ .... + d

₁

• B

¹

+ d

₀

• B

⁰

+ d

_-1

• B

^-1

+ ... + d

_-m

• B

^-m

(26)

Virgola fissa"

Esercizio: 23.625

₁₀

= ???

₂

"

(usare la rappresentazione in virgola fissa con n=8, m=8)"

Conversione parte intera:

23 : 2 = 11 resto 1 11 : 2 = 5 resto 1 5 : 2 = 2 resto 1 2 : 2 = 1 resto 0 1 : 2 = 0 resto 1

Conversione parte frazionaria:

0.625 x 2 = 1.25 parte intera 1 0.25 x 2 = 0.50 parte intera 0 0.50 x 2 = 1 parte intera 1

Soluzione: 23.625 = 00010111.10100000

(27)

Numeri con virgola mobile"

Un numero reale R può essere scritto in base B come "

R = ± m • B

^e  m = mantissa  

e = esponente  B = base"

Esempi con B = 10"

–  R1 = 3.1569 x 10³"

–  R2 = 2054.00035 x 10^-6"

–  R3 = 0.1635 x 10²"

–  R4 = 0.0091 x 10^-12"

Notazione scientifica: m = 0 . d_-1...d_-k "

Notazione scientifica normalizzata: m = d₀ . d_-1...d_-k con d₀ ≠ 0"

(28)

Numeri binari in virgola mobile"

Rappresentando mantissa ed esponente in binario in notazione scientifica normalizzata si ottengono numeri del tipo:"

" ±1.xx…x • 2^yy...y!

Si osservi che:"

Spostare la virgola (punto) a destra di n bit significa decrementare di n "

lʼesponente"

es: 0.01 • 2³ = 1.0 •2¹ "

Infatti 1 • 2^-2 • 2³ = 1 • 2^1"

Spostare la virgola (punto) a sinistra di n bit significa incrementare di n!

lʼesponente "

es: 100.011 • 2³ = 1.00011 • 2⁵ "

(29)

Numeri FP"

Esercizio: 10

₁₀

= ???

₂

FP"

Esercizio: 151.25

₁₀

= ???

₂

FP"

10

₁₀

= 1010

₂

= 1010.0

₂

• 2⁰

= 1.01

• 2³

151

₁₀

= 128 + 16 + 4 + 2 + 1 = 10010111

₂

0.25

₁₀

x 2 = 0.50

₁₀

parte intera 0

0.50

₁₀

x 2 = 1

₁₀

parte intera 1 0.25

₁₀

= 0.01

₂

Quindi = 151.25

₁₀

= 10010111.01

₂

= 1.001011101

₂

• 2⁷

(30)

Numeri FP"

Una volta fissato il numero di bit totali per la rappresentazione dei numeri razionali rimane da decidere:"

- Quanti bit assegnare per la mantissa ?"

(maggiore è il numero di bit e maggiore è lʼaccuratezza con cui"

si riescono a rappresentare i numeri)"

- Quanti bit assegnare per lʼesponente ?"

(aumentando i bit si aumenta lʼintervallo dei numeri rappresentabili)"

OVERFLOW: si ha quando lʼesponente positivo è troppo grande "

per poter essere rappresentato con il numero di bit"

assegnato allʼesponente "

UNDERFLOW: si ha quando lʼesponente negativo è troppo grande"

(in valore assoluto) per poter essere rappresentato"

(31)

Standard IEEE754: Singola precisione (32 bit) "

Lʼintervallo di valori (decimali) rappresentabili è ± ~10^-44.85 -- ~10^38.53"

Standard IEEE754: Doppia precisione (64 bit)"

Lʼintervallo di valori (decimali) rappresentabili è ± ~10^-323.3 -- ~10^308.3!

Numeri FP in standard IEEE754"

(32)

Esempio: scrivere -10. 625₁₀ in notazione floating point, usando lo standard IEEE754 in singola precisione"

Standard IEEE754: Esempio"

- 10.625₁₀ = - (10 + 0.5 +0.125) = - (2³ + 2¹ + 1/2 + 1/8) = "

"= - 1010. 101₂ = - 1. 010101 • 2³ = "

"= (-1)¹ • (1 + 0.010101) • 2^3"

Aggiungendo allʼesponente la polarizzazione il numero diventa: "

(-1)¹ • (1 + 0.010101) • 2^(3+127)"

(33)

Esempio: Quale numero decimale rappresenta la seguente sequenza di bit, letta secondo lo standard IEEE754?"

Standard IEEE754: Esempio"

esponente: 10001101₂ = 128+8+4+1=141_10"

mantissa: 1+0.10011₂= 1 + 0.5 + 0.0625 + 0.03125 = 1.59375_10"

Quindi il numero è: 1.59375₁₀ • 2(141 - 127) = 1.59375₁₀ • 2^14"

oppure:"

1,10011 * 2¹⁴ = 110011000000000 = 16384+8192+1024+512 = 26112"

(34)

Somma di numeri FP"

Shift Somma Normalizzazione

Arrotondamento

(35)

Esercizio: Dati i due numeri esadecimali A=C3160000 e B=42F80000"

1.  tradurre i numeri in binario"

2.  interpretare le sequenze di bit ottenuti come numeri FP espressi secondo lo standard IEEE754 in singola precisione "

3.  eseguirne poi la somma specificando tutti i passaggi"

4.  rappresentare il risultato ottenuto in esadecimale"

Somma di numeri FP con standard IEEE754"

Soluzione:"

1. Traduzione in binario"

A = 1100 0011 0001 0110 0000 0000 0000 0000 B = 0100 0010 1111 1000 0000 0000 0000 0000 2. Interpretazione di A e B come numeri FP:"

A = 1 10000110 00101100000000000000000 B = 0 10000101 11110000000000000000000 cioè:"

A = (-1)¹ • 1.001011 • 2^10000110 = (-1)¹ • 1.001011 • 201111111 + 111"

B = (-1)⁰ • 1.1111 • 2^10000101 = (-1)⁰ 1.1111 201111111 + 110"

(36)

3. Somma"

  lʼesponente di A è 2⁷ mentre quello di B è 2⁶. Allineando B si ottiene:"

A = 1.001011 B = 0.111110"

  A è negativo e quindi eseguo il complemento a due aggiungendo un bit per il segno"

A = 10.110101 B = 00.111110"

  somma delle mantisse"

A = 10.110101 +"

B = 00.111110"

---"

C = 11.110011 è un numero negativo il cui valore assoluto è 0.001101 ""

Somma di numeri FP con standard IEEE754"

(37)

  normalizzazione"

C = (-1)¹• 0.001101 • 2^10000110 = (-1)¹ • 1.101 • 201111111 + 100"

e quindi"

C = 1 10000011 10100000000000000000000

= 1100 0001 1101 0000 0000 0000 0000 0000 4. Rappresentazione di C in esadecimale"

C = C1D00000"