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

Esercizi di conversione decimale base N

alla posizione.Esempio: convertire (302) in base 10.7La cifra meno signi cativa indica il coeciente di 7 ,0quella piu signi cativa il coeciente di 7 , per cui2 (302) = 3 7 + 0 7 + 2 72 1 07 = 3 49 + 0 7 + 2 1= 147 + 0 + 2= 149c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.5Esercizi - conversione base N decimale!Convertire in base 10 i seguenti numeri espressi nellebasi 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.6Esercizi - conversione base N decimale!Convertire in base 10 i seguenti numeri espressi nellebasi 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]

SN-AB.7Conversione 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, 1, 2, ..., 7) è esprimibile nella corrispondente codifica binaria (000, 001, 010, ..., 111) su 3 cifre binarie

ogni cifra esadecimale (0, 1, 2, ..., F) è esprimibile nella corrispondente codifica binaria (0000, 0001, 0010, ..., 1111) su 4 cifre binarie

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

SN-AB.8Esempi - 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

# # # # # #

1 1 2 4 2 6

Quindi: (01001010100010110) = (112426)2 8

A D(3) Convertire in binario

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

A D( ) (3) ( )

16 16 16

# # #

(1010) (0011) (1101)

2 2 2

A

Quindi: (3) = (101000111101)₁₆ 2c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.9Esercizi - conversione base N base M!

Convertire i seguenti numeri nelle basi indicate:

(10010101001010) in base 82 [R. 22512]

(11110101101000) in base 162 [R. 3D68]

(13277) in base 28 [R. 1011010111111]

B E(0 9) in base 216 [R. 1011000011101001]

(214) in base 25 [R. 111011]

(354) in base 67 [R. 510]

(821) in base 129 [R. 477]

(821) in base 89 [R. 1233]

(821) in base 169 [R. 29B]c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.10Esercizi - conversione base N base M!

Convertire i seguenti numeri nelle basi indicate:

AC B(29) in base 816 [R. 2541233]

(34772) in base 168 [R. 39FA]

(1011) in base 139 [R. 44B]

(312) in base 416 [R. 30102]

(1492) in base 1511 [R. 87B]

C(14) in base 1615 [R. A9F]

C(14) in base 815 [R. 5237]

(558) in base 129 [R. 322]c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.11Addizioni e sottrazioni

in binarioSi e ettuano secondo le regole del sistema decimale,ossia sommando (sottraendo) le cifre di pari pesoSi suppone di non avere limitazione sul numero dicifre binarie (bit) disponibili.

Esempio: e ettuare la somma binaria 11110+101001

1 11 1 1 1 0 +
1 0 1 0 0
1 1 0 0 1 0 ;

Esempio: e ettuare la di erenza binaria 1011 011011

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, sipuo avere un sul bit di peso immediatamenteriportosuperiore, o un dal bit di peso immediata-prestitomente superiore.

Nella numerazione binaria questi sono detti rispetti-carry borrowvamente 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 [R. 1101111]

(225) + (63)₁₀ 10 [R. 100100000]

(229) + (111)₁₀ 10 [R. 101010100]

;(10) (6)₁₀ 10 [R. 100]

;(39) (14)₁₀ 10 [R. 11001]

;(32) (7)₁₀ 10 [R. 11001]

;(84) (37)₁₀ 10 [R. 101111]

;(18) (7)₁₀ 10 [R. 1011]

;(25) (15)₁₀ 10 [R. 1010]

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

Over owNel caso in cui si abbia un numero limitato di bit adisposizione (come avviene nella realta), si possonoavere 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 owQuesta condizione si dice condizione di .c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.15

Esempi - over owConsiderando numeri binari di 4 bit, e ettuare lasomma 9 + 7 (9) = (1001)₁₀ 2(7) = (0111)₁₀ 21 0 0 1 +0 1 1 11 0 0 0 0Il 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 11 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 irestanti N-1 il valore assoluto del numero, in binariopuro. S modulo0: segno +;1: segno

In questa notazione esistono due rappresentazionidel numero 0: ;!::: +00 0 0 ;! ;::: 01 0 0c 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 massimoe 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 = 1001c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.18

Conversione da decimale a complemento a due: se il numero è positivo, la corrispondente rappresentazione in C.A. 2 è costituita dal modulo del numero in binario a cui viene aggiunto il bit di segno con valore zero (MSB). Se il numero è negativo:

• si scrive il corrispondente numero positivo in rappresentazione C.A. 2
• si complementano tutti i bit
• si somma 1

Le ultime due operazioni rappresentano l'operazione di "complemento a due" di un numero binario.

Osservazioni: i numeri negativi hanno sempre bit di segno = 1. Esiste una sola rappresentazione dello 0: (0 0).

Rappresentazione in complemento a due

Un modo alternativo per calcolare il "complemento a due" di un numero binario negativo è il seguente:

Considerando il numero da destra a sinistra, eseguo le seguenti operazioni:

1. copio tutti gli zeri fino a trovare il primo uno
2. copio l'uno
3. complemento i restanti bit

Esempio:

2 al numero, infatti (( ) ) = numero numeroCA CA2 2c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.22

Conversione da complemento a due a decimale - esempio

Scrivere il numero decimale corrispondente al numero 100101 in complemento a due su 6 cifre

Il numero (100101) è negativo, quindi CA2 prima sottraggo 1, ottenendo (100100). Complementando i bit ottengo