Codifica dei numeri: Appunti di Informatica

La codifica dei numeri: notazione posizionale

Dato un numero N₁₀ in base 10 contenente m cifre scritto come A_m-1A_m-2...A₀, questo corrisponde a:

N₁₀ = A_m-1 x 10^m-1 + A_m-2 x 10^m-2 + ... + A₀ x 10⁰

(A_m-1A_m-2...A₀)₁₀ = Σ A_i x 10ⁱ, A_i ∈ A₁₀

Esempio di conversione

Esempio: (852)₁₀ = 8 x 10² + 5 x 10¹ + 2 x 10⁰

Con m cifre in A₁₀ quanti numeri posso esprimere = 10^m

Considerando gli interi positivi posso scrivere tutti i numeri tra [0, 10^m-1]

Esempi di rappresentazioni posizionali

• m = 4, p = 7, copre [0, 7⁴ - 1] (cioè [0, 2400])
• m = 1, p = 13, copre [0, 13 - 1] (cioè [0, 12])
• m = 2, p = 13, copre [0, 13^-1] (cioè [0, 28560])

All'aumentare di p cresce il potere espressivo del decimale.

Altre codifiche

Codifica ottale (in base 8)

A₈ = {0, 1, 2 ... 7}

Con m cifre in A₈ scrivo numeri da [0, 8^m-1]

Codifica esadecimale (in base 16)

A₁₆ = {0, 1 ... 9, A, B, C, D, E, F}

Per la conversione A₁₆, A₁₀ ... = 15

Con m cifre in A₁₆ scrivo numeri da [0, 16^m-1]

Conversioni

Binario ⇒ Decimale

(101)₂ = 1 x 2² + 0 x 2¹ + 1 x 2⁰ = (5)₁₀

(110010)₂ = 1 x 2⁵ + 1 x 2⁴ + 0 x 2² + 0 x 2² + 1 x 2¹ + 0 x 2⁰ = (39)₁₀

Decimale ⇒ Binario

537 | 2 = 265 + 1
265 | 2 = 132 + 1
132 | 2 = 66 + 0
66 | 2 = 33 + 0
33 | 2 = 16 + 1
16 | 2 = 8 + 0
8 | 2 = 4 + 0
4 | 2 = 2 + 0
2 | 2 = 1 + 0
1 | 2 = 0 + 1
Si comincia dal basso verso l’alto ⇒ (531)₁₀ = (1000001001)₂

NB: L'ultimo resto è sempre = 1

Codifica dei numeri: notazione posizionale

Dato un numero N₁₀ in base 10 contenente m cifre scritto come A_m-1A_m-2...A₀, questo corrisponde a:

N₁₀ = A_m-1 × 10^m-1 + A_m-2 × 10^m-2 + ... + A₀ × 10⁰

(A_m-1,A_m-2...A₀)₁₀ = ∑_i=0^m-1 a_i × 10ⁱ, a_i ∈ A₁₀

Esempio di conversione

Esempio: (852)₁₀ = 8 × 10² + 5 × 10¹ + 2 × 10⁰

Con m cifre in A₁₀ quanti numeri posso esprimere: 10^m

Considerando gli interi positivi, posso scrivere tutti i numeri tra [0,10^m-1]

Esempi con rappresentazione posizionale

• m = 3, p = 7, copre [0,7³-1] (cioè [0,2400])
• m = 2, p = 13, copre [0,13²-1] (cioè [0,12])
• m = 4, p = 13, copre [0,13^-1 (cioè [0,2856])

All’a crescere di p cresce il potere espressivo del dizionario.

Altre codifiche

Codifica ottale (in base 8)

A₈ = {0,1...7}

Con m cifre in A₈ scrivo numeri da [0,8^m-1]

Codifica esadecimale (in base 16)

A₁₆ = {0,1...9, A, B, C, D, E, F}

Per le conversioni A₁₆ in A₁₀ m = 15

Con m cifre in A₁₆ scrivo numeri da [0,16^m-1]

Conversioni

Binario ⇒ Decimale

(101)₂ = 1 × 2² + 0 × 2¹ + 1 × 2⁰ = (5)₁₀

(1100010)₂ = 1 × 2⁶ + 1 × 2⁵ + 0 × 2⁴ + 0 × 2³ + 0 × 2² + 1 × 2¹ + 0 × 2⁰ = (98)₁₀

Decimale ⇒ Binario

53 / 2
26 + 1
26 / 2
13 + 0
13 / 2
6 + 1
6 / 2
3 + 0
3 / 2
1 + 1
1 / 2
0 + 1

⇒ (53)₁₀ = (110101)₂

(0 + i.e. resto della divisione di intere) NB: L'ultimo resto è sempre = 1

Conversione ottale/esadecimale → decimale

(623)₈ = 6 × 8² + 2 × 8¹ + 3 × 8⁰ = 6 × 64 + 16 + 3 = (403)₁₀

(623)₁₆ = 6 × 16² + 2 × 16¹ + 3 × 16⁰ = 6 × 256 + 32 + 3 = (1541)₁₀

(A10)₁₆ = A × 16³ + 1 × 16² + 0 × 16¹ = 10 × 4096 + 256 + 7 × 16 = (44329)₁₀

Conversione decimale → ottale/esadecimale

Si fanno le conversioni passando dalla rappresentazione binaria e

Esprimere ogni sequenza di 3 numeri binari se è in base 8 (2³=8) (1234)₁₀ = (10011010010)₂ (040 041 100 111)₂ (2 3 1 7)₈ (1234)₁₀ = (23478)₈

Esprimere ogni sequenza di 4 numeri binari se è in base 16 (2⁴=16) (1234)₁₀ = (10011010010)₂ (0100 1100 1111)₂ (4 C F)₁₆ (1234)₁₀ = (4CF)₁₆

Somma tra numeri binari

Si esegue in colonna e si opera cifra per cifra:

• 0 + 0 = 0 riporto 0
• 1 + 0 = 1 riporto 1
• 0 + 1 = 1 riporto 1
• 1 + 1 = 1 riporto 1

Esempio 0101 + 1 (5)₁₀ 1001 = (9)₁₀ 1110 (14)₁₀

I numeri interi

È possibile dedicare il primo bit alla codifica del segno:

• "1" il numero che segue è negativo
• "0" il numero che segue è positivo

Con m cifre in binario e codifica modulo e segno posso rappresentare tutti i numeri nell'intervallo X ∈ [-2^m-1+1, 2^m-1-1]

Esempi

• 01101₂ = +13
• 11101₂ = -13
• -27 = 01101011122 = 01111010

Rappresentazione in complemento a 2 (CP2)

Date m cifre binarie, disponibili 2^m configurazioni distinte.

In CP2 se ne usano:

• 2^m-1 - 1 per valori positivi
• -1 per lo zero
• -2^m-1 per i valori negativi

Sia x ∈ [-2^m-1, 2^m-1-1] il numero da rappresentare in CP2, con m bit.

• Se x è positivo o nullo, scrivo x in binario con m bit.
• Se x è negativo, scrivo 2^m - x in binario con m bit.

Questo equivale alla seguente codifica: N_CP2 = a_m-1 ... a₁ a₀ - a_m-1 x 2^m-1 + a_m-2 x 2^m-2 + ... + a₀ x 2⁰

= -a_m-1 x 2^m-1 + Σ a_i x 2ⁱ, a_i ∈ {0,1}

[viene cambiato il segno alla cifra più significativa]

Rappresentazione modulo e segno

• -3 = 111
• -2 = 110
• -1 = 101
• -0 = 100
• +0 = 000
• +1 = 001

Il primo bit indica il segno; se lo cambio, ottengo il numero opposto

Rappresentazione in CP2 (m=3)

• -4 = 100
• -3 = 101
• -2 = 110
• -1 = 111
• 0 = 000
• +1 = 001

Il primo bit indica sempre il segno del numero, però se lo cambio non ottengo il numero opposto

Esempio

Definire un intervallo che contenga -23 e -45

m=6? vediamo ... copre [-2⁵, 2⁵-1] = [-32, 31] NO

m=7? vediamo ... copre [-2⁶, 2⁶-1] = [-64, 63] OK!

• -23 → 2⁷ - 23 = 128 - 23 = 105 = (1101001)_CP2
• -45 = (01011001)_CP2

NB Occorre utilizzare sempre m bit, se non avessimo messo lo zero iniziale in (45)_CP2 avrei ottenuto un numero negativo a 6 bit!

Conversione decimale → CP2

Metodo operativo per rappresentare X ad n bit

Controllo che X ∈ [-2^n-1, 2^n-1 - 1], altrimenti n bit non bastano

• Se X è positivo, scrivo X utilizzando n bit
• Ricordarsi: di aggiungere uno zero o più di uno se necessario all'inizio del numero!
• Se X è negativo:
  1. Scrivo X utilizzando n bit
  2. Complemento tutti i bit di X (1 → 0, 0 → 1)
  3. Sommo 1 al numero ottenuto

Esempio: Scrivere -54 in CP2 con il numero di bit necessari

• n = 7 copre [-2⁶, 2⁶-1] = [-64, 63]

Scrivo (54)₁₀ → Q 110110

Complemento → 10011001

Sommo 1 1₂ 10011010

Conversione CP2 → decimale

Possiamo usare la definizione: N_CP2 = a_n-1 a_n-2 ... a₀ - a_m-1 x 2^m-1 + a_m-2 x 2^m-2 ... + a₀ x 2⁰

Esempio

• (1001000)_CP2 = -2⁶ + 2³ = -64 + 8 = (-56)₁₀
• (10011011)_CP2 = -2⁷ + 2⁴ + 2² + 2¹ + 2⁰ = (-103)₁₀

NB: Convertire sempre in decimale, con questo metodo si può controllare che le operazioni siano corrette

Somma tra numeri in CP2

In CP2 l'operazione di somma algebrica è in realtà come nella rappresentazione binaria posizionale.

Grazie alla rappresentazione in CP2 è possibile eseguire anche sottrazioni tra numeri binari con lo stesso meccanismo.

Carry e overflow in CP2

In CP2 occorre ignorare il bit di carry (1), cioè il riporto in caso nel bit di coda non segno.

In CP2 occorre individuare l'overflow (1).

Quando c'è overflow il risultato è inconsistente con gli addendi.

Somma di due addendi positivi può dare un numero negativo.

Somma di due addendi negativi può dare un numero positivo.

NB Non può esserci overflow quando sommo due numeri di segno opposto.

Esempio

60 + (-54)
(60)₁₀ = (0 1 1 1 1 0 0)_cpl2 + (-54)₁₀ = (1 0 0 1 0 1 0)_cpl2 = (1) 0 0 0 0 1 0

Il risultato è [0000110]_cpl2 = (6)₁₀

Esempio

(100)_cpl2 + (101)_cpl2 1 0 0 + 1 0 1 = (1) 1 0 0 1

Overflow Si indica con {0,1} tra quadre [1] c'è [0] non c'è

- Il risultato non ha senso, occorre scrivere gli addendi con un bit in più per rappresentare il risultato dell'operazione.

Esempio

• -3 => 1 1 0 1
• m = 4 7 => 1 0 0 1

-10 => [1] (1) 0 1 1 0 Scrivere che -10 è [0110]_cpl2 non ha senso quindi è come se fosse [0 0 1 0]_cpl che è effettivamente -10, ma si scrive così: [1] (1) 0 1 1 0 numero esempio negativo m = 4 +3 => 0 0 1 1 +6 => 0 1 1 0 +9 => [1] (1) 0 0 1

Scrivere che +9 è [100]_cpl2 non ha senso quindi è come se fosse [0 0 1 0 0]_cpl che è effettivamente +9, ma si scrive così: [1] (1) 0 0 1 numero positivo

I numeri frazionari

Si rappresentano anteponendo zero al numero

N_p = 0,a₁ a₂ a₃ ... a_n = a₁ x p^-1 + a₂ x p^-2 + a₃ x p^-3 + a_n x p^-n = ⁿ∑_i=-1 a_i x p^-i a_i ε A_p

In base 10

= 0,586 = 5 x 10^-1 + 8 x 10^-2 + 6 x 10^-3

In base 2

= (0,101)₂ = 1 x 2^-1 + 0 x 2^-2 + 1 x 2^-3 = 1/2 + 1/8 = (0,625)₁₀

NB: Date n cifre in base pⁿ posso rappresentare un sottinsieme dell'intervallo continuo [0,1 - 2^-m] e l'errore di approssimazione avrà un valore di 2^-m.

Conversione decimale -> binario su frazioni

L'algoritmo delle moltiplicazioni per convertire N₁₀ ε [0,1]

1. Moltiplico N₁₀ per 2
2. La parte intera del risultato definisce una cifra della rappresentazione binaria finale
3. La parte frazionaria viene moltiplicata per 2
4. Si itera 1.3 fino a:
   • ottenere parte frazionaria nulla (rappresentazione esatta) oppure
   • coprire tutte le cifre binarie a disposizione (rappresentazione approssimata)
5. La cifra più significativa (il coefficiente di 2^-1) è dato dalla prima parte intera calcolata, quella meno significativa (il coefficiente di 2^-m) è dato dall'ultima parte intera calcolata

Esempio

Convertire in binario 0.625 utilizzando m = 3 bit

0,625 x 2 = 1 + 0,25
0,250 x 2 = 0 + 0,5
0,500 x 2 = 1 + 0
→ Parte intera + Parte frazionaria

Otteniamo (0,625)₁₀ = (0,101)₂

→ La parte intera definisce la rappresentazione binaria finale

Esempio

Convertire in binario 0,587 utilizzando m=6 bit

0,587 x 2 = 1 + 0,174
0,174 x 2 = 0 + 0,348
0,348 x 2 = 0 + 0,696
0,696 x 2 = 1 + 0,392
0,392 x 2 = 0 + 0,784
0,784 x 2 = 1 + 0,568

Otteniamo (0,587)₁₀ ≈ (0,100101)₂

La rappresentazione è approssimata → la parte frazionaria finita non = 0.

L'accuratezza però è almeno 2^-6.

Esempio

Convertire in binario 0,9 utilizzando m=16 bit

0,9 x 2 = 1 + 0,8
0,8 x 2 = 1 + 0,6
0,6 x 2 = 1 + 0,2
0,2 x 2 = 0 + 0,4
0,4 x 2 = 0 + 0,8
0,8 x 2 = 1 + 0,6
0,6 x 2 = 1 + 0,2

Otteniamo (0,9)₁₀ = (0,1110011001100110)₂ con accuratezza di almeno 2^-16.

Rappresentazione in virgola fissa

Uso m bit e n bit per parte intera e frazionaria (es: m=8 bit e n=6 bit → tot 16 bit)

Per rappresentare (-123,24)₁₀

• -123₁₀ = (10000001)_CP2
• 0,24₁₀ ≈ (001101)

⇒ (-123,24)₁₀ ≈ (10000001,001101)₂

Questa rappresentazione mi dà:

• Precisione costante lungo ℝ
• Estremi definiti solo da m

Rappresentazione in virgola mobile (Floating Point)

Il numero in base p in virgola mobile è espresso come:

• m = mantissa (numero frazionario con segno)
• b = base della notazione esponenziale (numero naturale)
• n = caratteristica (numero intero)
• p = base
• Uso: I₁ bit per rappresentare m e I₂ bit per n

NB: La base p della codifica può essere diversa della base della rappresentazione in floating point b

Esempio

(p=10, b=10):

• 333.6875 = 3.336875 x 10² m = 0.336875, m=3
• Se b=2 (p=2: binario) m=1101, e m=11 = 0.6875 x 10¹
• Normalizzazione

A parità di precisione numero di cifre dopo la virgola può cambiare giocando sull'esponente

Esempio: 0.6789012345 x 10⁵ = 6.789012345 x 10⁴ (normalizzato)

Un numero è detto normalizzato se contiene una sola cifra nella parte intera

La forma normalizzata è vantaggiosa se numero di cifre (bit) disponibili per rappresentare m è limitato, ciò permette di evitare zeri superflui iniziali

La normalizzazione permette, a parità di cifre usate per la mantissa, una maggiore precisione

Standard IEEE 754-1985 a 32 bit (precisione singola)

Si usa sempre b=2 e p=2

Il numero X viene scritto così: X = (-1)^S x 1.M x 2^E

• S = Segno (1 bit)
• M = Mantissa in forma normalizzata (23 bit)
• E = la Caratteristica (8 bit) obiettisce l'esponente n
• S, M, E si rappresentano in base b=2