Corso di Fondamenti di Informatica - dei.unipd.itfilira/fi/etc/rappresentazione.pdf · • alfabeto...

1

Fond. di Informatica Rappresentazioni binarie 1

Corso di

Fondamenti di Informaticahttp://www.dei.unipd.it/~satta/teach/java/index.html

Giorgio Satta

Dipartimento di Ingegneria dell’ Informazionehttp://www.dei.unipd.it/~satta

[email protected]

2


Unità• b = bit (binary digit)

• B = Byte = 8b

Multipli• K = 210 = 1024 ≈ 103 [Kilo]

• M = 220 ≈ 106 [Mega]

• G = 230 ≈ 109 [Giga]

• T = 240 ≈ 1012 [Tera]

Rappresentazione

Unita` elementare di informazione e` il bit, pari ad una variabile che assumevalore su di un insieme binario. I calcolatori digitali trattano esclusivamente informazione codificata in forma binaria.Il livello di rappresentazione binario e` masherato all’utente. Introduci la nozione di macchina a strati sovrapposti (Tosotatti, pg.3).

3


Rappresentazione

Interi : Notazione posizionale base 2 • alfabeto = {0, 1}

• N2 = an an -1 … a1 a0, n ≥ 0, ai ∈ alfabeto

• conversione dalla base 2 alla base 10 :

2n × an + 2n -1 × an - 1 + … + 21 × a1 + 20 × a0

• esempio :

11012 → 23 × 1 + 22 × 1 + 21 × 0 + 20 × 1 = 1310

Il sistema posizionale puo` essere utilizzato per basi diverse da quella decimalenormalmente impiegata.

4


Rappresentazione

Interi : Notazione posizionale base 16 • alfabeto = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}

• N16 = an an -1 … a1 a0, n ≥ 0, ai ∈ alfabeto


16n × an + 16n -1 × an - 1 + … + 161 × a1 + 160 × a0

• esempio :

B7F16 → 162 × 11 + 161 × 7 + 160 × 15 = 294310

La base esadecimale viene spesso utilizzata per rappresentare piu` agevolmentenumeri binari. (Vedi anche base ottale.)

5


Rappresentazione

Interi : Notazione posizionale base p• alfabeto = {0, 1, 2, …, p -1}

• Np = an an -1 … a1 a0, n ≥ 0, ai ∈ alfabeto

• conversione dalla base p alla base 10 :

p n × an + p n -1 × an - 1 + … + p 1 × a1 + p 0 × a0

Forma generale per la notazione posizionale in base arbitraria.

6


Interi : Notazione posizionale base p• conversione dalla base 10 alla base p

– input N

– algoritmo

d ← ⎣ logp N ⎦for i = 0 to d

ai ← N mod pN ← N div p

Rappresentazione

La notazione ⎣n⎦ rappresenta la parte intera del numero n. Es: ⎣8.6⎦ equivale a 8. Nota che vengono utilizzate d + 1 cifre. L’operatore div esegue la divisione intera tra due numeri. Es: 11 div 4 = 2. L’operatore mod restituisce il resto della divisione intera tra due numeri. Es: 11 mod 4 = 3.

7


Rappresentazione

Interi 10 → p : Esempio• p = 2, N = 87, d = ⎣ log2 87 ⎦ = 6

a0 = 1 N = 43a1 = 1 N = 21a2 = 1 N = 10a3 = 0 N = 05a4 = 1 N = 02a5 = 0 N = 01a6 = 1 N = 00

8710 → 10101112

6 < log2(87) < 7.Cenno alla conversione binaria <-> esadecimale per quartine (Tosoratti pg. 27).

8


Rappresentazione

Frazionari : Notazione posizionale base 2 • alfabeto = {0, 1}

• Np = 0 . a-1 a-2 … a-n +1 a-n , n ≥ 1, ai ∈ alfabeto


2-1 × a-1 + 2-2 × a-2 + … + 2-n +1 × a-n +1 + 2-n × a-n

• esempio :

0.10112 → 2-1 × 1 + 2-2 × 0 + 2-3 × 1 + 2-4 × 1= 0.687510

Utilizzo il punto per separare la parte frazionaria dalla parte intera, come danotazione anglosassone. Assumo la parte intera sia 0.

9


Rappresentazione

Frazionari : Notazione posizionale base p• alfabeto = {0, 1, 2, …, p -1}

• Np = 0 . a-1 a-2 … a-n +1 a-n , n ≥ 1, ai ∈ alfabeto

• conversione dalla base p alla base 10 :

p -1 × a-1 + p -2 × a-2 + … + p -n +1 × a-n +1 + p -n × a-n

Forma generale.

10


Frazionari : Notazione posizionale base p• conversione dalla base 10 alla base p

– input N

– algoritmoi = -1repeat

ai ← ⎣N × p⎦N ← (N × p ) - ⎣N × p⎦i ← i - 1

until N = 0

• l’algoritmo potrebbe non terminare

Rappresentazione

La notazione ⎣n⎦ rappresenta la parte intera del numero n. Es: ⎣8.6⎦ equivale a 8. L’espressione (N × p ) - ⎣N × p⎦ rappresenta la parte frazionaria del numeroN × p . Numeri razionali non periodici in una base possono diventare periodici in una diversa base. (Provare a convertire 0.110 in base 2.) Se il prodotto della conversione risulta essere periodico, e` necessario fermare l’esecuzione dell’algoritmo.

11


Rappresentazione

Frazionari 10 → p : Esempio• p = 2, N = 0.625

a-1 = 1 N = 0.25a-2 = 0 N = 0.50a-3 = 1 N = 0.00

0.62510 → 0.1012

12


Rappresentazione

Reali : Notazione floating point• b = base (intero)

• S = +1 / -1

• E = esponente (intero)

• F = mantissa (frazionario)

• conversione alla base 10 :

S × F × b E

La mantissa puo` avere parte intera e/o frazionaria diversa da zero, a secondadelle convenzioni.

13


Rappresentazione

Floating Point : Esempio• b = 10, S = +1, E = 11, F = 3.49

• conversione alla base 10 :

+ 349 000 000 000

14


Interi senza segno su n bit• conversione :

– N10 → N2

– aggiungo zeri a sinistra sino a n bit

• esempio (n = 3) :

• range : [ 0, 2n - 1 ]

Rappresentazione macchina

001 011 100 101 111110010000

0 1 4 753 62

Le successive rappresentazioni sono relative alla macchina. Mentre le rappresentazioni matematiche esaminate in precedenza non pongono limitazioninella codifica, la macchina adotta una rappresentazione necessariamente finitaper i numeri.Il metodo senza segno applica una semplice conversione a base binaria. Eventualibit disponibili a sinistra vengono posti a 0. La nozione di range deriva dalla imposizione che la rappresentazione sia finita.

15


Modulo e segno su n bit• conversione :

– ⏐N10⏐ → N2

– aggiungo zeri a sinistra sino a n -1 bit

– an = 0 se N10 ≥ 0 ; an = 1 se N10 ≤ 0


• range : [-2n - 1 + 1, 2n - 1 - 1 ]


001 011 100 101 111110010000

0 1 0 -3-13 -22

Il metodo modulo e segno applica una conversione binaria del modulo limitataagli n-1 bit piu` a destra. Eventuali bit disponibili a sinistra vengono posti a 0. Il bit piu` a sinistra, rappresentato qui da an, codifica il segno. Il numero 0 ha due rappresentazione, dunque la codifica e` ridondante. La rappresentazione comporta inoltre alcuni problemi con l’algoritmo di somma(vedi oltre).

16


Complemento a 2 su n bit• conversione (traslazione asse negativi) :

– N2 se N10 ≥ 0 ; (N10 + 2n )2 se N10 < 0



• range : [-2n - 1, 2n - 1 - 1 ]


001 011 100 101 111110010000

0 1 - 4 -1-33 -22

Il metodo complemento a due applica una conversione binaria se il numero e` non negativo, altrimenti applica una conversione binaria sul numero traslato. Eventuali bit disponibili a sinistra vengono posti a 0. Cio` si applica solamente ainumeri positivi, poiche` i negativi comportano sempre l’intera occupazione degli n bit disponibili. Il bit piu` a sinistra codifica il segno. Il numero 0 ha una sola rappresentazione. La rappresentazione e` monotona, cioe` procedendo da sinistra a destra nell’asse i numeri rappresentati crescono, ad eccezione del salto dal massimo numeropositivo rappresentabile al minimo numero negativo rappresentabile.

17


Modulo e segno• 2 rappresentazioni per il valore 0

• algoritmi di somma differenti a seconda del segno(non posso eseguire la somma per colonne)

Complemento a 2• una sola rappresentazione per lo 0 (un valore in più

disponibile nel range rispetto al modulo e segno)

• posso applicare l’algoritmo di somma per colonne


Vantaggi del complemento a 2 rispetto al modulo e segno. Vedi oltre per l’algoritmo di somma.

18


Complemento a 2 : Somma• somma per colonne

+ 2 0 0 1 0 - 5 1 0 1 1- 5 1 0 1 1 - 2 1 1 1 0___ ______ ___ ______

- 3 1 1 0 1 - 7 (1) 1 0 0 1


Algoritmo di somma per colonne. Parto dalla colonna piu` a destra, chiamata C1, e procedo verso sinistra conteggiando gli eventuali riporti, sino all’ultimacolonna, chiamata Cn. Osservare che la presenza di un riporto originato sulla colonna Cn non identificanecessariamente un errore nella rappresentazione del risultato ottenuto.

19


Complemento a 2 : Overflow• regola

si ha overflow se e solo se esiste un solo riportosulle colonne Cn -1 e Cn

- 5 1 0 1 1 + 5 0 1 0 1- 5 1 0 1 1 + 4 0 1 0 0___ ______ ___ ______

error 0 1 1 0 error 1 0 0 1


Il fenomeno di overflow (trasbordo) indica che il range a disposizione dellarappresentazione non e` sufficiente per rappresentare il risultato della sommacorrente. La presenza di un riporto originato alla colonna Cn non indica necessariamenteun overflow. La presenza di overflow puo` essere rilevata conteggiando eventualiriporti presenti alle colonne Cn-1 e Cn. Tale conteggio deve essere pari ad 1 (dunque se il conteggio e` 2 oppure 0 non vi e` overflow).

20


Complemento a 2 : Cambio segno• algoritmo :

– identificare l’occorrenza più a destra del simbolo 1– complementare tutti i bit a sinistra dell’occorrenza

identificata


+ 52 0 0 1 1 0 1 0 0

- 52 1 1 0 0 1 1 0 0


Algoritmo di complementazione o cambio segno: Parto dal bit piu` a destra e procedo verso sinistra sino ad incontrare la prima occorrenza del simbolo 1. Tuttii simboli piu` a sinistra di tale occorrenza devono venire complementati. Algoritmo alternativo (ed equivalente): Complemento tutti i bit e sommo 1 al bit piu` a destra. Posso utilizzare l’algoritmo di cambio segno per ridurre operazioni di differenzaad operazioni di somma algebrica. Posso inoltre utilizzare nella conversione di un numero negativo dalla base decimale alla rappresentazionecomplemento a due.

21


Eccesso k su n bit• consideriamo il caso k = 2n -1

• conversione (traslazione intero asse) :

– (N10 + 2n -1)2


• esempio (n = 3):

• range : [-2n - 1, 2n - 1 - 1 ]


001 011 100 101 111110010000

- 4 - 3 0 31- 1 2- 2

L’eccesso k non presenta alcuna discontinuita` nella crescita dei numeri rappresentati procedendo da sinistra verso destra. Diversamente dalle precedenti codifiche, per l’eccesso k abbiamo an = 0 se N10 < 0, an = 1 se N10 ≥ 0.

22


Reali : Standard IEEE• S = 0 / +1

• E = intero eccesso M (binario)

• F = frazionario binario normalizzato in modo tale che il bit più significativo corrisponda ad a0 e sia omesso

• conversione dallo standard ad un numero reale :

-1S × 1.F × 2E - M

• numeri molto vicini in prossimità dello zero, moltodistanti al crescere del valore assoluto


Standard per la virgola mobile stabilito dall’organizzazione internazionale IEEE (Institute for Electical and Electronic Engineering) ed approvato dall’ANSI(American National Standards Institute).Ciascun numero reale viene rappresentato in virgola mobile mediante un bit per ilsegno S, alcuni bit per l’esponente E (rappresentato in eccesso M) ed alcuni bit per la parte frazionaria F che deve essere normalizzata in modo tale che il bit piu` significativo (il bit piu` a sinistra) corrisponda ad a0. La regola di conversione al numero reale rappresentato e` quella sopraspecificata. Vi e` una eccezione alla regola nel caso in cui E ed F siano compostidi soli zeri: in tale caso il bit corrispondente a a0 deve essere posto a 0. Cio` serve per poter rappresentare il numero reale 0.0, la cui rappresentazione risulterebbealtrimenti impossibile. Rappresentazione non uniforme: non vi e` una distanza fissa tra due numeriadiacenti nella rappresentazione.

23


Reali : Standard IEEE (cont.)• le specifiche per la rappresentazione di S, E, M ed F

variano a seconda delle diverse precisioni


singola doppia quadruplaS (b) 1 1 1E (b) 8 11 15M (val) 127 1023 32767F (b) 23 52 112tot (B) 4 8 16

24


Standard IEEE : Esempio• XIEEE = 11000011 11010000 00000000 00000000

= 1 10000111 10100000000000000000000

• conversione ad un numero reale :

– S = 1

– E = 100001112 = 13510

– F = 0.1012 = 0.62510

– X = (-1)1 × 2135 - 127 × 1.625 = - 41610


25


Standard IEEE : Esempio• X = 42.6875

= 101010.10112= 1.010101011 × 25

• conversione alla precisione singola :

– S = 0

– E = 5 + 127 = 132 = 10000100

– F = 01010101100000000000000

– XIEEE = 0 10000100 01010101100000000000000= 01000010 00101010 11000000 00000000


I processori in commercio adottano lo standard IEEE nella rappresentazione deinumeri in virgola mobile. Esiste pero` una differenza: mentre le architetture di tipo big endian riportano in memoria i singoli byte della rappresentazionenell’ordine regolare, le architetture little endian invertono tale ordine. Esempi di architettura big endian sono Motorola, IBM, Sun ed altri processori RISC. Esempi di architettura little endian sono Digital ed Intel.

26


Codice ASCII• ASCI = American Standard Code for Information

Interchange • utilizzato per la rappresentazione dei caratteri più

comuni, divisi in– alfanumerici : a - z, A - Z, 0 - 9– segni : + / ? ; : …– comandi : return, tab, ...


La codifica ASCII e` uno Standard ANSI.

27


Codice ASCII• 7 bit utilizzati, valori nel range [0 .. 127] :

– non stampabili codificati in [0 .. 31]– A-Z codificati in [65 .. 90] – a-z codificati in [97 .. 122]– 0-9 codificati in [48 .. 57]

• valori consecutivi rispetto all’ordine alfabetico


I valori [128 .. 255] sono detti ASCII esteso, e vengono utilizzati per carratteri di lingua non Inglese (caratteri accentati, ecc). Tali valori non sono utilizzati in modo standard (le codifiche cambiano a seconda del costruttore.

28


Unicode• progettato per rappresetare i caratteri di tutte le

lingue conosciute• prima versione: codici a due Bytes• seconda versione: codici rappresentati da una o due

unità di codifica di 2 Bytes • esempio :

– { = x007B– ښ = x069A


Corso di Fondamenti di Informatica - dei.unipd.itfilira/fi/etc/rappresentazione.pdf · • alfabeto...

Documents

Transcript of Corso di Fondamenti di Informatica - dei.unipd.itfilira/fi/etc/rappresentazione.pdf · • alfabeto...