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 e

: : :

posizionale (unita, decine, centinaia, )

decimale (cifre = 0,1,2,3,4,5,6,7,8,9)

In altre parole:

208 = 2 10 + 0 10 + 8 10

2 1 0

Altri sistemi di numerazione di interesse sono an-

ch'essi posizionali, ma con base diversa da 10.

sistema base cifre

binario 2 01

ottale 8 01234567

: : :

esadecimale 16 0 9 A B C D E F

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

Conversione decimale base N

!

Si e ettuano 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.

10 ;

53 26 13 6 3 1 0 quozienti

107 ;

1 1 0 1 0 1 1 resti

;

107 21 4 0 quozienti

;

2 1 4 resti

;

107 6 0 quozienti

;

11 6 resti

I resti sono in base 10, quindi devono essere conver-

titi in base N: (11) = (B) .

2 16

Quindi 107 = (1101011)

10 2

= (412) 5

B

= (6 ) 16

c 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 spe-

ci cate:

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]

c 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 spe-

ci cate:

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]

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

Conversione base N decimale

!

Partendo dalla cifra piu signi cativa, si moltiplica

la cifra per il valore della base, elevata alla potenza

corrispondente alla posizione.

Esempio: convertire (302) in base 10.

7

La cifra meno signi cativa indica il coeciente di 7 ,

0

quella piu signi cativa il coeciente di 7 , per cui

2

(302) = 3 7 + 0 7 + 2 7

2 1 0

7

= 3 49 + 0 7 + 2 1

= 147 + 0 + 2

= 149

c 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 indicati:

(1000101) 2 [R. 69]

(477) 8 [R. 319]

F

(40 ) 16 [R. 1039]

(3074) 5 [R. Impossibile]

(5778) 9 [R. 4283]

(126) 9 [R. 105]

(781) 16 [R. 1921]

B

(3 8)

13 [R. 658]

c 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 indicati:

(10010) 8 [R. 4104]

EA

(2 )

16 [R. 746]

F

(369 1) 15 [R. Impossibile]

(5669) 11 [R. 7456]

(94598) 10 [R. 94598]

(889) 12 [R. 1257]

(1110) 3 [R. 1065]

(1357) 8 [R. 751]

c 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 e sempli -

cato perche:

: : :

ogni cifra ottale (0, , 7) e esprimibile nella

: : :

corrispondente codi ca binaria (000, , 111) su

3 cifre binarie

: : :

ogni cifra esadecimale (0, , F) e esprimibile

: : :

nella corrispondente codi ca binaria (0000, ,

1111) su 4 cifre binarie

c 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

2

Partendo dalla cifra meno signi cativa si considerano

la cifre binarie rispettivamente a gruppi di 3:

01 001 010 100 010 110

# # # # # #

1 1 2 4 2 6

Quindi: (01001010100010110) = (112426)

2 8

A D

( 3 )

Convertire in binario

16

Scriviamo le singole cifre esadecimali come numeri

binari di 4 cifre:

A D

( ) (3) ( )

16 16 16

# # #

(1010) (0011) (1101)

2 2 2

A D

Quindi: ( 3 ) = (101000111101)

16 2

c 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

2 [R. 22512]

(11110101101000) in base 16

2 [R. 3D68]

(13277) in base 2

8 [R. 1011010111111]

B E

( 0 9) in base 2

16 [R. 1011000011101001]

(214) in base 2

5 [R. 111011]

(354) in base 6

7 [R. 510]

(821) in base 12

9 [R. 477]

(821) in base 8

9 [R. 1233]

(821) in base 16

9 [R. 29B]

c 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:

AC B

( 29 ) in base 8

16 [R. 2541233]

(34772) in base 16

8 [R. 39FA]

(1011) in base 13

9 [R. 44B]

(312) in base 4

16 [R. 30102]

(1492) in base 15

11 [R. 87B]

C

( 14) in base 16

15 [R. A9F]

C

( 14) in base 8

15 [R. 5237]

(558) in base 12

9 [R. 322]

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

Addizioni e sottrazioni in binario

Si e ettuano 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: e ettuare la somma binaria 11110+10100

1 1 1

1 1 1 1 0 +

1 0 1 0 0

1 1 0 0 1 0 ;

Esempio: e ettuare la di erenza binaria 1011 0110

1

1 0 1 1 -

0 1 1 0

0 1 0 1

c 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

puo avere un sul bit di peso immediatamente

riporto

superiore, o un dal bit di peso immediata-

prestito

mente superiore.

Nella numerazione binaria questi sono detti rispetti-

carry borrow

vamente e .

Le somme (di erenze) bit a bit possono essere de -

nite come segue: ;

0+0=0 0 0=0

;

1+0=1 1 0=1

;

0+1=1 1 1=0

;

1 + 1 = 0 (carry=1) 0 1 = 1 (borrow=1)

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

Esercizi - somme e sottrazioni in binario

E ettuare le seguenti operazioni in binario puro:

(34) + (77)

10 10 [R. 1101111]

(225) + (63)

10 10 [R. 100100000]

(229) + (111)

10 10 [R. 101010100]

;

(10) (6)

10 10 [R. 100]

;

(39) (14)

10 10 [R. 11001]

;

(32) (7)

10 10 [R. 11001]

;

(84) (37)

10 10 [R. 101111]

;

(18) (7)

10 10 [R. 1011]

;

(25) (15)

10 10 [R. 1010]

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

Over ow

Nel caso in cui si abbia un numero limitato di bit a

disposizione (come avviene nella realta), si possono

avere due casi particolari:

carry sul bit piu signi cativo (MSB)

borrow dal bit piu signi cativo (MSB)

In entrambi i casi il numero di bit ssato non e suf-

ciente per rappresentare il risultato. over ow

Questa condizione si dice condizione di .

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

Esempi - over ow

Considerando numeri binari di 4 bit, e ettuare la

somma 9 + 7 (9) = (1001)

10 2

(7) = (0111)

10 2

1 0 0 1 +

0 1 1 1

1 0 0 0 0

Il risultato non e rappresentabile su 4 bit: over ow.

Considerando numeri binari di 4 bit, e ettuare la

;

di erenza 4 7 (4) = (0100)

10 2

(7) = (0111)

10 2

(1) 0 1 0 0 -

0 1 1 1

1 1 0 1

Il risultato non e rappresentabile su 4 bit: over ow.

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

Rappresentazione in modulo e segno

E' uno dei modi per rappresentare numeri interi re-

lativi su un numero ssato di bit.

Dati N bit, il bit piu signi cativo indica il segno, ed i

restanti N-1 il valore assoluto del numero, in binario

puro. S modulo

0: segno +

;

1: segno

In questa notazione esistono due rappresentazioni

del numero 0: ;!

::: +0

0 0 0 ;! ;

::: 0

1 0 0

c 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