Informatica - Digitalizzazione dei numeri

Ad es duecentocinquanta = 250 in base 10

­ Esadecimale

0 1 2 3 4 5 6 7 8 9 B A C D E F

Ad es duecentocinquanta = FA in base 16

Per convertire un numero da binario a decimale si usa la formula: N10=dn*2^n + d(n­1)*2^(n­1) +

... + d1*2^1 + d0*2^0

Ad esempio 1001=1*2^3 + 0*2^2 + 0*2^1 + 1*2^0 = 9

Algoritmo di conversione (decimale in esadecimale)

X: numero da convertire

B: base in cui convertire

|

Q=X (assegnamento)

N=0 (contatore)

| ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­|

Q==0 ­ si ­ stop Q=quoziente_di(Q/B)

| |

­ ­ ­ no ­ R = resto_di(Q/B) ­ convertire R in RB ­ mettere R in posizione N ­ incrementare N di 1

Conversione da Esadecimale in decimale

Moltiplico ogni cifra per le potenze della base 16. Ad es 4F= 4*16^1 + F*16^0 = 4*16 + 15*1 =79

Conversione da Esadecimale in binario

Sostituisco ogni cifra Esadecimale con il suo corrispettivo in binario.

Esempi di notazione Esadecimale

0 0b0000 0x0

4 0b0011 0x4

10 0b1010 0xA

14 0b1110 0xE

15 0b111 0xF

Aritmetica “Modulo 2^N”

in 4 bit si possono rappresentare numeri fino al 15. Se l’INPUT è maggiore di 15? Il computer

ignora l’errore e prosegue, il 16 sarà rappresentato come 0. In realtà la sequenza dei numeri in

quei 4 bit non rappresenta un numero ma l’intera famiglia dei multipli di quel numero pari a 2^N,

dove N è il numero di bit.

|M|(2^N) modulo 2^N → se M1=kM (con k numero intero), allora |M1|(2^N)=|M|(2^N)

Algoritmo

Tesi di Church: solo funzioni parzialmente ricorsive possono essere calcolate con algoritmi.

Un algoritmo deve essere: preciso (indica ogni volta la sequenza corretta di ogni passo),

deterministico (ogni volta che si applica deve produrre lo stesso risultato), finito (deve

comportare un numero finito di passi).

La definizione di un algoritmo si compone di tre parti: Input (ciò che è impegnato nel processo),

processo (elaborazione dei passaggi), Output (terminazione).

Variabile: contenitore di simboli o valori. Ogni variabile ha un nome per distinguerle dalle altre e

questo è anche l’indirizzo dove la variabile sta nella memoria.

= (Istruzione di assegnamento, la variabile assume quel valore)

== (verifica che il valore della variabile coincide con quello dopo l’istruzione)

Addizione di numeri naturali

I numeri si sommano bit a bit

ad esempio

1 … 111010 + (X)

0 … 111010 = (Y)

­­­­­­­­­­­­­­­­­­­

? … 110100 (S)

S=|X+Y|(2^N)

Se il riporto è 1 ottengo errore di oversize

S=0 ←→ ZF=1

rN=0 ←→ CF=1

Per sommare numeri si possono usare circuiti detti “Full­Adder”.

I bit saranno scritti mano a mano nei registri del processore (EFLAG)

EFLAG 01111101 …. 001 1 11101 0

ZF CF

Sottrazione di numeri naturali

D=|X­Y|(2^N) = |X­Y+2^N| = |1+X­Y+2^N­1| = 1+X+compl(Y)|. Utilizzando in full­adder, se faccio il

complemento di Y, la somma mi dà la differenza.

D=0 ←→ ZF=1

uN=1 ←→ CF=1

Traslazioni

Se traslo un numero verso sinistra, aggiungo 0 a destra e faccio scorrere gli altri bit. Ottengo

così moltiplicazione x2 (se il bit a sinistra scartato è 1 ottengo errore di oversize).

Se traslo un numero verso destra, aggiungo 0 a sinistra e faccio scorrere gli altri bit. Ottengo

così divisione x2 (se il bit a destra scartato è 1 ottengo errore di oversize).

Per confrontare due valori X e Y si sottrae il secondo dal primo e:

ZF=1 ←→ X=Y

ZF=0 ←→ X!=Y

ZF=1 oppure CF=1 ←→ X≤Y

CF=0 ←→ X≥Y

CF=1 ←→ X<Y

CF=0 e ZF=0 ←→ X>Y

Numeri interi

Modulo e segno

Rappresento un numero intero come |numero| se numero>=0 oppure |numero|+2^(N­1) se

numero =< 0

Ad esempio +1 ­­> 0001, ­6 ­­> 1110

In pratica aggiungo un bit per il segno 0 (+) e 1 (­). Si presenta il problema del +0 (0000) e ­0

(1000).

Rappresentazione di interi per complemento a 2

|numero| se numero >= 0, 2^N ­ |numero| se numero < 0

Ad esempio con N=4

+1 ­­> 0001, ­6 ­­> 1010

Traslazione

|numero|+2^(N­1) se numero >= 0, 2^(N­1) ­ |numero| se numero < 0

Ad esempio con N=4

+1 ­­> 1001, ­6 ­­> 0010

Operazioni in base 2 per interi

Se Rx e Ry sono le rappresentazioni ad N bit in complemento a 2 di due numeri interi x e y,

allora la rappresentazione della loro somma s, esprimibile su N bit, è data da: Rs=|Rx+Ry|(2^N)

Similmente la rappresentazione della loro differenza è data da: Rd=|Rx­Ry|(2^N)

I numeri sono universalmente rappresentati nei calcolatori in complemento a 2.

Numeri reali

In VIRGOLA FISSA (+75.04, ­0.156)

In VIRGOLA MOBILE (+0.7504 x dieci^2, ­15.6 x dieci^(­2))

Scomposizione numeri reali

0.625=6+2+5 in posizione ­1, ­2, ­3, in base 10

0.101=1+0+1 in posizione ­1, ­2, ­3, in base 2 = 0.625

110.101=1+1+0+1+0+1 in posizione 2, 1, 0, ­1, ­2, ­3, in base 2 = 6.625

Posso scomporre 6.625 in 6 (110) e 0.625 (101)

IEEE 754

Standard per il calcolo della virgola mobile

Esistono in questo standard quattro formati per i numeri in virgola mobile: a precisione singola

(32bit), a precisione doppia (64bit), precisione singola estesa (>=43bit), precisione doppia

estesa (>=79bit)

Numeri a precisione singola

Su 32 bit: da 0 a 22 bit si rappresenta la mantissa (naturale che corrisponde alla componente

frazionaria del numero in virgola fissa con una sola cifra a sinistra del punto decimale), da 22 a

30 bit si rappresenta l'esponente (con traslazione di 127), infine il 31 bit rappresenta il segno (0 o