Universita degli Studi di FerraraLaurea triennale in Matematica

Corso di Programmazione

L’aritmetica dei calcolatori

Filippo Mantovani05 Ottobre 2009

Burocrazia:

Segnate sul foglio A4 che faro girare tra i banchi:

1. COGNOME e NOME

2. E-MAIL

3. Una X nella colonna LAB-CARD nel caso vogliate farerichiesta della card.

Riceverete per e-mail il nome utente e la password per accederealle sezioni riservate del sito DI QUESTO CORSO.

Fine burocrazia!

Filippo Mantovani - 05/10/2009 – 2 –

Programmare sı, ma cosa?!?

Prima di alzarci in volo e im-parare a programmare (qual-siasi cosa questo voglia dire),dobbiamo avere un’idea, al-meno vaga, di cosa stiamoper programmare (ed even-tualmente sapere quali sono leuscite d’emergenza)!

Filippo Mantovani - 05/10/2009 – 3 –

Alcune domande (per la nostra sicurezza)

I Come si memorizzano/rappresentano i dati in un calcolatore?E come avvengono le operazioni matematiche?

I Perche tanta importanza alle memorie? E perche tanti tipidiversi di memoria (RAM, dischi, cache)?

I Come e fatta e come si comanda una CPU?

I ...

Filippo Mantovani - 05/10/2009 – 4 –

Fidarsi e bene, ma...

Filippo Mantovani - 05/10/2009 – 5 –

Introduzione:

Il nostro sistema di numerazione e IN BASE 10 (dieci) ed ePOSIZIONALE:

10881 = 1 · 10000 + 0 · 1000 + 8 · 100 + 8 · 10 + 1= 1 · 104 + 0 · 103 + 8 · 102 + 8 · 101 + 1 · 100

= diecimilaottocentottantuno

OSSIA:

1. Le cifre del nostro sistema di numerazione sono:0, 1, 2, 3, 4, 5, 6, 7, 8 e 9.

2. La stessa cifra assume significati diversi dipendentementedalla posizione che occupa in un dato numero.

Filippo Mantovani - 05/10/2009 – 6 –

Un esempio antico...

“Il sistema decimale, comune alla maggior parte delle civilta, sia

antiche che moderne, era stato sostituito in Mesopotamia da una

notazione che aveva a fondamento la base sessanta. Molto e stato

scritto sui motivi che avrebbero dato origine a questo cambiamento; e

stata avanzata l’ipotesi che possano avervi contribuito considerazioni

di carattere astronomico o che il sistema sessagesimale sia risultato

dalla combinazione di due sistemi piu antichi, uno decimale, l’altro in

base sei. Appare pero piu verosimile l’ipotesi che la base sessanta sia

stata consapevolmente adottata e riconosciuta come fondamentale ai

fini della misurazione: una grandezza di sessanta unita puo venire

infatti facilmente divisa in meta, terzi, quarti, quinti, sesti, decimi,

dodicesimi, quindicesimi, ventesimi e trentesimi, offrendo cosı dieci

suddivisioni possibili.”Carl B. Boyer, Storia della matematica

Filippo Mantovani - 05/10/2009 – 7 –

Un esempio antico...

Scopriamo cosı che:data una base B possiamo

rappresentare qualsiasinumero come somma di

multipli di potenzesuccessive della base B.

10000 = 7200 + 2760 + 40

= 2 · 602 + 46 · 601 + 40 · 600

= (2; 46; 40)base 60

=

Filippo Mantovani - 05/10/2009 – 8 –

Un po’ piu in generale...

Filippo Mantovani - 05/10/2009 – 9 –

Riflessione sulla distribuzione dei numeri...

Filippo Mantovani - 05/10/2009 – 10 –

Non solo base 10

Base 16 [Esadecimale]r = 16; Cifre: xi ∈ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,A,B ,C ,D,E ,F

N16 =∑

i

xi(16)i

NB: Solitamente i numeri esadecimali sono preceduti dal prefisso 0x .

Esempio: 15dec = Fhex = 0xF

Base 8 [Ottale]r = 8; Cifre: xi ∈ 0, 1, 2, 3, 4, 5, 6, 7

N8 =∑

i

xi(8)i

NB: Solitamente i numeri ottali sono preceduti dal prefisso 0.

Esempio: 15dec = 17oct = 017

Filippo Mantovani - 05/10/2009 – 11 –

Non solo base 10 [Un po’ piu esotico]

Base√

2r =√

2; Cifre: xi ∈ 0, 1

N√2 =∑

i

xi(√

2)i

O’ famo strano?!?

Filippo Mantovani - 05/10/2009 – 12 –

Da base 10 a base B

IN GENERALE:Dato un numero N rappresentato in base 10, le cifre di N in unaqualsiasi base B sono i resti delle divisioni successive di N per labase di destinazione B .

ESEMPIO: (25)10 = (11001)2 = (34)7

Filippo Mantovani - 05/10/2009 – 13 –

Da base B a base 10

IN GENERALE:Sia dato un numero N rappresentato su C cifre in una basegenerica B . Allora possiamo rappresentare (N)10 calcolando

(N)10 =C−1∑i=0

σiBi

dove σi rappresenta il valore in base 10 della cifra i − esima di(N)B partendo dalla meno significativa.

ESEMPI:(135)10 = 1 · 102 + 3 · 101 + 5 · 100

(234)7 = 2 · 72 + 3 · 71 + 4 · 70

(10A)16 = 1 · 162 + 0 · 161 + 10 · 160

PS: Horner’s method...

Filippo Mantovani - 05/10/2009 – 14 –

Shortcut method for r = bg and R = bG

Esempio: Hex → Bin; Bin → Hex

Filippo Mantovani - 05/10/2009 – 15 –

Shortcut method for r = bg and R = bG

Esempio: Hex → Bin; Bin → Hex

Filippo Mantovani - 05/10/2009 – 16 –

Rappresentazione binaria (senza segno) –1–

ESEMPIO:

(1101)2 = (1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 )10

= (1 · 8 + 1 · 4 + 0 · 2 + 1 · 1 )10

= (8 + 4 + 0 + 1 )10

= (13)10

(1101)2 prende il nome di rappresentazione binaria su 4 bitdel numero decimale 13.

NB:Il bit piu a destra e detto bit meno significativo(least significant bit = LSB).Il bit piu a sinistra e detto bit piu significativo

(most significant bit = MSB).

Filippo Mantovani - 05/10/2009 – 17 –

Rappresentazione binaria (senza segno) –2–

Nelle architetture a 32 bit, le istruzioni sono lunghe 32 bit...Su 32 bit il numero (13)10 appena visto lo rappresentiamo cosı:

NB: Anche in base 10 gli zeri a sinistra non contano: 000013 = 0013 = 13

Se consideriamo solo i numeri positivi, con 32 bit possiamorappresentare l’intervallo di numeri interi compreso tra0 e (232 − 1) ossia [0; 4 294 967 295].

(0000 0000 0000 0000 0000 0000 0000 0000)2 = (0)10

(0000 0000 0000 0000 0000 0000 0000 0001)2 = (1)10

(0000 0000 0000 0000 0000 0000 0000 0010)2 = (2)10

... ...(1111 1111 1111 1111 1111 1111 1111 1110)2 = (4 294 967 294)10

(1111 1111 1111 1111 1111 1111 1111 1111)2 = (4 294 967 295)10

Filippo Mantovani - 05/10/2009 – 18 –

Rappresentazione binaria (con segno) –1–

DOMANDA:

Quanti/quali valori possiamo rappresentare con 4 bit?

Filippo Mantovani - 05/10/2009 – 19 –

Complemento a due

Con 32 bit il cerchio sarebbe ovviamente troppo grande...

(0000 0000 0000 0000 0000 0000 0000 0000)2 = +(0)10

(0000 0000 0000 0000 0000 0000 0000 0001)2 = +(1)10

(0000 0000 0000 0000 0000 0000 0000 0010)2 = +(2)10

... ...(0111 1111 1111 1111 1111 1111 1111 1110)2 = +(2 147 483 646)10

(0111 1111 1111 1111 1111 1111 1111 1111)2 = +(2 147 483 647)10

(1000 0000 0000 0000 0000 0000 0000 0000)2 = −(2 147 483 648)10

(1000 0000 0000 0000 0000 0000 0000 0001)2 = −(2 147 483 647)10

(1000 0000 0000 0000 0000 0000 0000 0010)2 = −(2 147 483 646)10

... ...(1111 1111 1111 1111 1111 1111 1111 1110)2 = −(2)10

(1111 1111 1111 1111 1111 1111 1111 1111)2 = −(1)10

Questo modo di rappresentare i numeri binari con segno prende ilnome di rappresentazione in complemento a due.

Filippo Mantovani - 05/10/2009 – 20 –

Complemento a due (proprieta – 1 – )

Filippo Mantovani - 05/10/2009 – 21 –

Complemento a due (proprieta – 2 – )

I La meta positiva dei numeri, quelli da 0 a (231 − 1), usa lastessa rappresentazione del caso senza segno;

I si assume che il numero (1000...000)2 prenda il valore−(231)10;

I tutti gli altri numeri da (100...001)2 a (111...111)2 formanouna serie crescente di numeri negativi.

NOTA: La rappresentazione in complemento a duecomprende un numero negativo −(231) che non ha uncorrispondente numero positivo.Ossia, su 32 bit non riusciamo a rappresentare il numeropositivo +(231), ma riusciamo a rappresentare il suoopposto −(231).

Filippo Mantovani - 05/10/2009 – 22 –

Complemento a due (proprieta – 3 – )

I Cambio di segnoPer cambiare di segno a un numero basta:

I negare bit a bit il numero dato;I sommare 1.

I Estensione del segnoSe dobbiamo sommare due numeri con segno, marappresentati su un numero di bit differente dobbiamoestendere il segno di quello rappresentato su meno bit.Consideriamo il bit piu significativo (quello del segno) e locopiamo a sinistra tante volte quante sono i bit mancanti perarrivare alla rappresentazione dell’altro numero.

Filippo Mantovani - 05/10/2009 – 23 –

E nella “PROGRAMMAZIONE”...

...a cosa serve tutto cio?!?

I tipi in C...

Filippo Mantovani - 05/10/2009 – 24 –

Riflessione (per il programmatore coscienzioso)...

Quando programmiamo dobbiamo tenere conto dellarappresentazione dei numeri sul calcolatore.

In generale ha senso parlare di numeri naturali positivi e/onegativi, ma non ha senso, ad esempio, parlare di indirizzinegativi.

In C, ad esempio, definiremo int un numero intero con relativosegno, mentre unsigned int un numero intero senza segno.

Grazie a tali definizioni il compilatore trat-tera le variabili dichiarate nei due modiappena descritti.

Filippo Mantovani - 05/10/2009 – 25 –

Esempi

1. Rappresentiamo il numero positivo (13)10

in complemento a due su 8 bit:(13)10 = (00001101)2

2. Rappresentiamo ora il numero negativo −(13)10 incomplemento a due su 8 bit:

(13)10 = (00001101)2 → nego bit a bit → (11110010)2

→ aggiungo 1 → (11110011)2

ho cosı ottenuto −(13)10 = (11110011)2

3. Estendiamo il segno di −(13)10 a 16 bit:−(13)10 = (11110011)2 = (1111111111110011)2

Filippo Mantovani - 05/10/2009 – 26 –

La somma binaria

Supponiamo di voler sommare i numeri (6)10 e (7)10

rappresentati su 6 bit:

OSSIA:La somma di due numeri positivi si esegue “in colonna” in mododel tutto analogo a quello usato per la somma con i numeri inbase 10 che ci hanno insegnato alle elementari.

Filippo Mantovani - 05/10/2009 – 27 –

La sottrazione binaria

Supponiamo di voler sottrarre i numeri (6)10 e (7)10 su 8 bit.

Notiamo subito che vale l’uguaglianza: 6− 7 = 6 + (−7)

E noi sappiamo come trovare (-7) in rappresentazione incomplemento a 2 su 8 bit:

(7)10 = (0000111)2 → nego bit a bit → (11111000)2

→ aggiungo 1 → (11111001)2

A questo punto posso eseguire la somma tra 6 e -7 come vistonella slide precedente...

OSSIA:La sottrazione e riconducibile a una somma tra numerirappresentati in complemento a due su un dato numero di bit.

Filippo Mantovani - 05/10/2009 – 28 –

L’operazione “shift”

Oltre alla somma e alla sottrazione, gia incontrate e del tuttoanaloghe a quelle in base 10, e comodo introdurre il concetto di

shift.Data una sequenza di bit, lo shift a destra di s bit equivale a unadivisione per 2s , mentre lo shift a sinistra di s bit equivale a unamoltiplicazione per 2s!!!

Filippo Mantovani - 05/10/2009 – 29 –

L’operazione “shift”

Esempi:

Supponiamo di voler moltiplicare per 2 il numero 7 dopo averlotrasformato in binario:

(7)10 = (111)2 → shift a sinistra di 1 bit→ (1110)2 = (14)10 = (7 · 2)10

Supponiamo di voler dividere per 4 il numero 16 dopo averlotrasformato in binario:

(16)10 = (10000)2 → shift a destra di 2 bit→ (100)2 = (4)10 = (16/4)10

Filippo Mantovani - 05/10/2009 – 30 –

Ancora piu in dettaglio...

Abbiamo visto che, a parte la base, il modo di “calcolare”utilizzato da un PC non e poi tanto diverso dal nostro: anche luiin fondo esegue le operazioni in colonna!

Ma come si traduce tutto questo veramente nell’hardware deinostri calcolatori?

Filippo Mantovani - 05/10/2009 – 31 –

Le operazioni logiche tra bit

ESERCIZIO:

Come si puo fare per selezionare solo i bit di indice dispari in unasequenza di 16 bit?

Filippo Mantovani - 05/10/2009 – 32 –

Half adder

Filippo Mantovani - 05/10/2009 – 33 –

Full adder

Filippo Mantovani - 05/10/2009 – 34 –

Tanti sommatori fanno...

Se colleghiamo insieme n sommatori (full adder) otteniamo unsommatore di numeri interi a n bit!!!

E questo sara quello che faremo d’ora in avanti...

Filippo Mantovani - 05/10/2009 – 35 –

La moltiplicazione

Possiamo vedere la moltiplicazione tra due numeri a n bit comeuna serie di n somme.(Tanto le somme ora le sappiamo fare benissimo...)

Filippo Mantovani - 05/10/2009 – 36 –

Algoritmo della moltiplicazione

Se il bit meno significativo delmoltiplicatore e 1, si somma ilmoltiplicando al prodotto; seno, si procede a passo succes-sivo. Nei due passi successi-vi si scala il moltiplicando ver-so sinistra ed il moltiplicatoreverso destra. Questi tre passisono ripetuti tante volte quan-ti sono i bit su cui sono rappre-sentati gli operandi (e.g. 32bit su macchine a 32 bit).

Filippo Mantovani - 05/10/2009 – 37 –

Esempio su 4 bit...

Supponiamo di voler moltiplicare (3)10 e (2)10...

Filippo Mantovani - 05/10/2009 – 38 –

Domande

Filippo Mantovani - 05/10/2009 – 39 –