Basi di dati - il sistema di numerazione e l'algebra booleana

Sistemi di numerazione e algebra booleana

Laura Farinetti, Claudio Fornaro, Antonio Lioy, Massimo Poncino

Dipartimento di Automatica e Informatica

Politecnico di Torino

Sistemi di numerazione

Il sistema di numerazione usuale è posizionale (unità, decine, centinaia, ...) decimale (cifre = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9). In altre parole:

208 = 2 * 10² + 0 * 10¹ + 8 * 10⁰

Altri sistemi di numerazione di interesse sono anch'essi posizionali, ma con base diversa da 10.

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.1

Conversione decimale base N

Si effettuano divisioni successive del numero dato per la base N; i resti delle singole divisioni, presi alla rovescia, rappresentano le cifre del numero nella base N.

Esempio: convertire 107 in base 2, 5 e 16.

I resti sono in base 10, quindi devono essere convertiti in base N: (11)₁₀ = (B)₁₆.

Quindi 107 = (1101011)₂ = (412)₅ = (6B)₁₆.

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.2

Esercizi - conversione decimale base N

Convertire i seguenti numeri decimali nelle basi specificate:

• 345 in base 2 [R. 101011001]
• 345 in base 8 [R. 531]
• 345 in base 16 [R. 159]
• 989 in base 5 [R. 12424]
• 417 in base 7 [R. 1134]
• 615 in base 9 [R. 753]
• 426 in base 2 [R. 110101010]
• 1042 in base 11 [R. 868]

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.3

Esercizi - conversione decimale base N

Convertire i seguenti numeri decimali nelle basi specificate:

• 6666 in base 16 [R. 1A0A]
• 4596 in base 4 [R. 1013310]
• 687 in base 16 [R. 2AF]
• 595 in base 5 [R. 4340]
• 111 in base 2 [R. 1101111]
• 656 in base 5 [R. 10111]
• 811 in base 16 [R. 32B]
• 1101 in base 8 [R. 2115]

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.4

Conversione base N decimale

Partendo dalla cifra più significativa, si moltiplica la cifra per il valore della base, elevata alla potenza corrispondente alla posizione.

Esempio: convertire (302)₇ in base 10.

La cifra meno significativa indica il coefficiente di 7⁰, quella più significativa il coefficiente di 7², per cui:

(302)₇ = 3 * 7² + 0 * 7¹ + 2 * 7⁰ = 3 * 49 + 0 * 7 + 2 * 1 = 147 + 0 + 2 = 149

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.5

Esercizi - conversione base N decimale

Convertire in base 10 i seguenti numeri espressi nelle basi indicate:

• (1000101)₂ [R. 69]
• (477)₈ [R. 319]
• (40F)₁₆ [R. 1039]
• (3074)₅ [R. Impossibile]
• (5778)₉ [R. 4283]
• (126)₉ [R. 105]
• (781)₁₆ [R. 1921]
• (3B8)₁₃ [R. 658]

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.6

Esercizi - conversione base N decimale

Convertire in base 10 i seguenti numeri espressi nelle basi indicate:

• (10010)₈ [R. 4104]
• (2EA)₁₆ [R. 746]
• (369F)₁₅ [R. Impossibile]
• (5669)₁₁ [R. 7456]
• (94598)₁₀ [R. 94598]
• (889)₁₂ [R. 1257]
• (1110)₃ [R. 1065]
• (1357)₈ [R. 751]

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.7

Conversione base N base M

In generale, conviene fare la conversione da base N a base 10, seguita dalla conversione da base 10 a base M.

Nel caso particolare in cui si debba passare dalla base 2 alle basi 8 o 16 (o viceversa), il calcolo è semplificato perché ogni cifra ottale (0, ..., 7) è esprimibile nella corrispondente codifica binaria (000, ..., 111) su 3 cifre binarie e ogni cifra esadecimale (0, ..., F) è esprimibile nella corrispondente codifica binaria (0000, ..., 1111) su 4 cifre binarie.

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.8

Esempi - conversione base N base M

(01001010100010110)₂ Convertire in ottale

Partendo dalla cifra meno significativa si considerano le cifre binarie rispettivamente a gruppi di 3:

01 001 010 100 010 110 = 112426₈

(AD3)₁₆ Convertire in binario

Scriviamo le singole cifre esadecimali come numeri binari di 4 cifre:

A = 1010, D = 1101, 3 = 0011

Quindi: (AD3)₁₆ = (101011010011)₂

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.9

Esercizi - conversione base N base M

Convertire i seguenti numeri nelle basi indicate:

• (10010101001010)₂ in base 8 [R. 22512]
• (11110101101000)₂ in base 16 [R. 3D68]
• (13277)₈ in base 2 [R. 1011010111111]
• (BE09)₁₆ in base 2 [R. 1011000011101001]
• (214)₅ in base 2 [R. 111011]
• (354)₆ in base 7 [R. 510]
• (821)₁₂ in base 9 [R. 477]
• (821)₈ in base 9 [R. 1233]
• (821)₁₆ in base 9 [R. 29B]

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.10

Esercizi - conversione base N base M

Convertire i seguenti numeri nelle basi indicate:

• (ACB29)₈ in base 16 [R. 2541233]
• (34772)₁₆ in base 8 [R. 39FA]
• (1011)₁₃ in base 9 [R. 44B]
• (312)₄ in base 16 [R. 30102]
• (1492)₁₅ in base 11 [R. 87B]
• (C14)₁₆ in base 15 [R. A9F]
• (C14)₈ in base 15 [R. 5237]
• (558)₁₂ in base 9 [R. 322]

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.11

Addizioni e sottrazioni in binario

Si effettuano secondo le regole del sistema decimale, ossia sommando (sottraendo) le cifre di pari peso. Si suppone di non avere limitazione sul numero di cifre binarie (bit) disponibili.

Esempio: effettuare la somma binaria

11110₂ + 101001₂ = 110010

Esempio: effettuare la differenza binaria

1011₂ - 0110₂ = 0101

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.12

Carry e borrow

Come nelle usuali operazioni su numeri decimali, si può avere un riporto sul bit di peso immediatamente superiore, o un prestito dal bit di peso immediatamente superiore.

Nella numerazione binaria questi sono detti rispettivamente carry e borrow.

Le somme (differenze) bit a bit possono essere definite come segue:

• 0 + 0 = 0
• 1 + 0 = 1
• 0 + 1 = 1
• 1 + 1 = 0 (carry=1)

• 0 - 0 = 0
• 1 - 0 = 1
• 1 - 1 = 0
• 0 - 1 = 1 (borrow=1)

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.13

Esercizi - somme e sottrazioni in binario

Effettuare le seguenti operazioni in binario puro:

• (34)₁₀ + (77)₁₀ [R. 1101111]
• (225)₁₀ + (63)₁₀ [R. 100100000]
• (229)₁₀ + (111)₁₀ [R. 101010100]
• (10)₁₀ - (6)₁₀ [R. 100]
• (39)₁₀ - (14)₁₀ [R. 11001]
• (32)₁₀ - (7)₁₀ [R. 11001]
• (84)₁₀ - (37)₁₀ [R. 101111]
• (18)₁₀ - (7)₁₀ [R. 1011]
• (25)₁₀ - (15)₁₀ [R. 1010]

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.14

Overflow

Nel caso in cui si abbia un numero limitato di bit a disposizione (come avviene nella realtà), si possono avere due casi particolari:

• Carry sul bit più significativo (MSB)
• Borrow dal bit più significativo (MSB)

In entrambi i casi il numero di bit fissato non è sufficiente per rappresentare il risultato. Questa condizione si dice condizione di overflow.

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.15

Esempi - overflow

Considerando numeri binari di 4 bit, effettuare la somma 9 + 7

(9)₁₀ = (1001)₂

(7)₁₀ = (0111)₂

1001 + 0111 = 0000

Il risultato non è rappresentabile su 4 bit: overflow.

Considerando numeri binari di 4 bit, effettuare la differenza 4 - 7

(4)₁₀ = (0100)₂

(7)₁₀ = (0111)₂

0100 - 0111 = 1101

Il risultato non è rappresentabile su 4 bit: overflow.

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.16

Rappresentazione in modulo e segno

È uno dei modi per rappresentare numeri interi relativi su un numero fissato di bit. Dati N bit, il bit più significativo indica il segno, ed i restanti N-1 il valore assoluto del numero, in binario puro.

Segno modulo:

• 0: segno +
• 1: segno -

In questa notazione esistono due rappresentazioni del numero 0:

• +0: 0000
• -0: 1000

© 1992 - 96 - L. Farinetti, C. Fornaro, A. Lioy, M. Poncino (POLITO - DAI) SN-AB.17

Esercizi - modulo e segno

Rappresentare in modulo e segno su 4 bit il massimo e minimo valore, le due rappresentazioni dello 0, i numeri +5 e -1.

Soluzione:

• Minimo numero = 1111 = -7
• Massimo numero = 0111 = +7
• -0 = 1000
• +0 = 0000
• +5 = 0101
• -1 = 1111