Upload
thiago-andrade-guimaraes
View
220
Download
4
Embed Size (px)
Citation preview
Introduo aos AlgoritmosFundamentos Parte II
Armazenamento de Dados e Representao Numrica
Dilson Lucas Pereira
Armazenamento de Dados
Dados
Dados podem ser: texto, imagens, udio, vdeo, etc Como o computador lida com todos estes tipos de
dados? Um computador para cada tipo? invivel Assume uma representao uniforme Todos os que entram no computador so transformados
para esta representao, e transformados de volta quando saem
Padro de bits
Dados
Bit: 0 ou 1 Byte: 8 bits Padro de bits: sequncia (ou string) de bits
001010001010100001100101000010... Como a memria sabe que tipo de dados aquele padro
representa? No sabe! de responsabilidade do programa e dispositivos de entrada e
sada dar sentido ao padro
Texto
Texto uma sequncia de smbolos em alguma lngua
Geralmente cada smbolo representado por um padro de tamanho fixo
A = 10000001, B = 10000010, O nmero de smbolos que pode ser representado
depende do tamanho desta sequncia n bits 2n possibilidades
Padres
ASCII (ingls) : 7 bits (128 smbolos) ASCII estendido: 8 bits (256 smbolos) Unicode (outros idiomas): 16 bits (65536 smbolos) etc
Imagem
Formato bitmap e formato vetorial
Bitmap A imagem interpretada como
uma matriz de pixels (pontinhos) Cada pixel representado por
um padro que representa as informaes daquele pixel
Ex: RGB (red green blue) 1 byte para cada cor
Imagem
Vetorial A imagem decomposta
em pontos, linhas, curvas, polgonos, etc
Estes elementos podem ser representados por expresses matemticas
Bitmaps sofrem perda de qualidade quando aumentados
Imagens vetoriais no
Representao Numrica
O Sistema Decimal
o sistema numrico adotado mundialmente Base 10 (10 smbolos para cada dgito) Primeiro dgito: dezenas, segundo dgito: centenas,
terceiro dgito: milhares... Primeiro dgito: 100, segundo: 101, terceiro 102,... Ex: 1578 = 8x100 + 7x101 + 5x102 + 1x103
O Sistema Binrio
Tem base 2 Dois dgitos: 0 e 1 Primeiro dgito: 20, segundo: 21, terceiro, 22, Ex: 11110011 = 1x20 + 1x21 + 0x22 + 0x23 + 1x24 +
1x25 + 1x26 + 1x27 = 243
Converso Binrio-decimal
Multiplique cada dgito por seu peso, como no exemplo anterior
Ex: 0101101 = 1x20 + 0x21 + 1x22 + 1x23 + 0x24 + 1x25 + 0x26 = 45
Converso Decimal-binrio
Se d por meio de sucessivas divises:1. q nmero a ser convertido2. k 13. Se q = 0, pare. 4. Seno:
a) Divida q por 2. b) O resto se torna o k-simo dgito.c) q quociente d) k k + 1e) Volte ao passo 3
Converso Binrio-decimal
Ex: 45 45/2: r = 1 q = 22 22/2: r = 0 q = 11 11/2: r = 1 q = 5 5/2: r = 1 q = 2 2/2: r = 0 q = 1 1/2: r = 1 q = 0 101101
Ex: 37 37/2: r = 1 q = 18 18/2: r = 0 q = 9 9/2: r = 1 q = 4 4/2: r = 0 q = 2 2/2: r = 0 q = 1 1/2: r = 1 q = 0 100101
Representao de Inteiros
Ex: 134, 5, 7, -5, 0, etc Computadores consideram duas categorias de
inteiros: Inteiros com sinal e inteiros sem sinal Inteiros com sinal podem ser representados de trs
maneiras Sinal e magnitude Complemento de um Complemento de dois
Inteiros Sem Sinal Denota os inteiros de 0 ao infinito Obviamente o computador no pode armazenar todos estes
nmeros O maior inteiro disponvel depende da quantidade de
memria (bits) que o sistema usa para representar estes nmeros
n bits 2n nmeros Inteiros de 0 a 2n -1 32 bits: 0 a 4.294.967.295
Inteiros Sem Sinal
Para se armazenar um nmero inteiro sem sinal, realiza-se a converso conforme mostrado anteriormente
Se o nmero tiver mais que n bits, tem-se um overflow, seno, adicionam-se 0's esquerda at que o nmero tenha n bits
A representao sem sinal melhora ligeiramente a eficincia do armazenamento, uma vez que o computador no precisa armazenar informao relativa ao sinal
Ex: contagem, endereamento
Sinal e Magnitude
Neste formado, usa-se um bit para representar o sinal do nmero
0: positivo, 1: negativo Tem-se ento 1 bit a menos para representar o valor
absoluto do nmero em si Faixa: -2n-1-1 2n-1-1 32 bits: -2.147.483.647 -0 + 0 2.147.483.647 Note que existem dois 0's
+0 0000000 -0 1000000
Sinal e Magnitude
O processo para converter um nmero para este formato consiste em: Ignorar o sinal do nmero e convert-lo Se o nmero tiver menos de n-1 bits, adicionar 0's sua
esquerda at que se tenham n-1 bits Se o nmero for positivo, adicionar 0 sua esquerda, se
negativo, adicionar 1
Sinal e Magnitude
Para se converter de volta (interpretar), convertem-se os n-1 primeiros bits direita, adiciona-se o sinal de acordo com o ltimo bit
Este formato no utilizado por computadores Operaes como soma e subtrao no tem
implementao direta Tem dois 0's, pode confundir programadores
Complemento de Um
Neste formato, nmeros no negativos so representados da mesma maneira que inteiros sem sinal
Nmeros negativos so representados como o complemento de sua contraparte positiva
Nmeros cujo primeiro bit 0 so no-negativos, nmeros cujo primeiro bit 1 so no-positivos
0 aparece duas vezes +0 00000000 -0 11111111
Complemento de Um
Faixa: -2n-1-1 2n-1-1 32 bits: -2.147.483.647 -0 + 0 2.147.483.647 Representao:
Ignore o sinal, converta o nmero para binrio adicione 0's esquerda at que se tenham n bits Se o sinal (do nmero original) for negativo,
complemente o nmero, isto , inverta os 0's e 1's
Complemento de Um
Ex: Represente +7 em 8 bits +7 111 00000111
Represente -258 em 16 bits 258 100000010 0000000100000010
1111111011111101
Complemento de Um
Interpretao Se o bit mais esquerda for 0
Converta para decimal Seno
Complemente o nmero Converta para decimal Coloque o sinal negativo
Ex: 11110110 00001001 9 -9
Complemento de Um
No usado na prtica Operaes aritmticas no so diretas Dois 0's
Oferece o fundamento para a representao em complemento de dois
Complemento de Dois
Para representar um nmero em complemento e dois Ignore o sinal, converta o nmero para binrio Se o nmero de bits for menor que n, adicione 0's
esquerda Se o sinal do nmero original for negativo, deixe os
primeiros bits direita, at o primeiro 1, inclusive, como esto. Complemente o restante
Complemento de Dois O primeiro bit representa o sinal A faixa de nmeros que pode ser representada -2n-1 2n-1-1 Existe apenas um 0 Converter 000000 resulta em 000000 Converter o menor nmero negativo passvel de
representao resulta em 100000
Representao utilizada pelos computadores
Complemento de Dois
Ex: +7 em 8 bits 111 00000111
-40 em 16 bits 101000 0000000000101000 1111111111011000
Complemento de Dois
Interpretao Se o bit mais esquerda for 0
Converta para decimal Seno
Deixe os primeiros bits direita, at o primeiro 1, inclusive, como esto. Complemente o restante
Converta para decimal Adicione o sinal
Ex: 11110110 00001010 10 -10
Operaes em Bits
Operaes em bits podem ser aritmticas ou lgicas Operaes aritmticas compreendem soma, subtrao,
multiplicao, diviso, etc... Operaes lgicas
Um bit pode ser 0 ou 1. O valor 0 pode ser interpretado como o valor lgico falso e 1 pode ser interpretado como verdadeiro.
Desta maneira, podemos aplicar operaes lgicas sobre estes bits
Operaes Aritmticas em Inteiros
Adio e subtrao Outras operaes geralmente podem ser construdas
baseando-se nestas duas Assume-se complemento de dois, representao
mais adotada
Adio em Complemento de Dois
A adio se d de maneira semelhante adio de nmeros em base decimal
Alinhamos os nmeros e somamos coluna por coluna Tambm pode ocorrer vai um 0+0=0 1+0=1 1+1= 2 = 10 em binrio (0 e vai um) 1+1+1= 3 = 11 em binrio (1 e vai um)
Adio em Complemento de Dois
Ex: 17+22 100010001 +0001011000100111
24+(-17)11111 00011000 + 11101111 00000111
O ltimo vai um ignorado
Overflow
127+3 (8 bits, {-128,...,127})
111111101111111 +0000001110000010 = -126
127+3 (9 bits, {-256,...,255})
1111111001111111 +000000011010000010 = 130
Subtrao
Para subtrair, somamos com o nmero negativo Ex: 101 62 = 101 + (-62)
Operaes lgicas
Unrias (um operando) ou binrias (dois operandos) Binrias: e (and), ou (or), ou exclusivo (xor) Unria: negao
E, ou, ou exclusivo
10011000 and0011010100010000
10011000 or0011010110111101
10011000 xor0011010110101101
Shift
Shift a esquerda: move os bits para a esquerda Equivalente a multiplicar o nmero por 2 Ex: 00111011 (59) 01110110 (118)
Shift a direita: move os bits para a direita Equivalente a dividir o nmero por 2 Ex: 00111011 (59) 00011101 (29)
Sistema de Excesso
Com n bits representamos 2n nmeros 0, 1, 2, , 2n-1 Se quisermos representar at K nmeros negativos
podemos fazer um mapeamento
0 1 2 K (K+1) (K+2) (2n-1)
-K -(K-1) -(K-2) -(K-K) 1 2 (2n-1-K)
Sistema de Excesso
Ex: Queremos representar at 20 nmeros negativos em um em inteiros de 6 bits
0 1 2 20 63
-20 -19 -18 0 43
Sistema de Excesso
Converso Adicione K ao nmero Converta para binrio, adicione 0's esquerda caso necessrio
Interpretao Converta para decimal Subtraia K
Ex: K = 127, 8 bits, nmero -25 -25+127 102 01100110
11111110 para decimal, K = 127 11111110 254 (-127) 127
Representao de Ponto-flutuante
Representao de nmeros reais Converta a parte decimal Converta a parte real Coloque o ponto entre as partes
A converso da parte inteira se d como j visto (sinal e magnitude)
Convertendo-se a Parte Real
Multiplicao sucessiva x nmero (menor que 1) a ser convertido k 1 Se x = 0 (ou a preciso desejada foi obtida), pare Seno
Multiplique x por 2. A parte inteira se torna o K-simo bit mais esquerda x parte real K K+1 Volte ao passo 3
Convertendo-se a Parte Real
Ex: 0,125 0,125 x 2 = 0,250 0,25 x 2 = 0,500 0,5 x 2 = 1,00 0.001 0x2-1 + 0x2-2 + 0x2-3
Ex: 0,875 0,875 x 2 = 1,75 0,75 x 2 = 1,5 0,5 x 2 = 1,00 0.111 1x2-1 + 1x2-2 + 1x2-3
Representao Real
Nem todo nmero pode ser representado exatamente em binrio
Ex: 0,1 0,2 0,45
Normalizao
Os nmeros so armazenados na forma normalizada1.xxxxxxxxxxxx
necessrio mover o ponto para a esquerda ou direita Mover para direita aumenta o nmero duas vezes, para a
esquerda diminui Ex: 1010001.1101 26 x 1.01000111001 -0.001110011 -2-3 x 1.110011
Sinal, Expoente e Mantissa
Os nmeros so armazenados em trs partes Sinal, Expoente e Mantissa
Ex: +1000111.0101 = +26 x 1.0001110101 Sinal: + Expoente: 6 Mantissa: a parte que sobra, apenas a parte aps o ponto
do nmero normalizado 0001110101
Padres IEEE
IEEE: Institute of Electrical and Electronic Engineers
Define 3 padres, 2 so adotados Preciso nica e preciso dupla
Preciso nica: 1 bit para o sinal, 8 para o expoente, 23 para a mantissa
Preciso dupla: 1 para o sinal, 11 para o expoente, 52 para a mantissa
Representao em Preciso nica
Armazene o sinal (0: positivo, 1: negativo) Armazene o expoente em formato de excesso, K =
127, adicione 0's esquerda caso necessrio Armazene a mantissa, adicione 0's direita caso
necessrio Ex: + 26 x 1.101000111001
Sinal: 0, expoente: 6, mantissa: 101000111001 01000010101000111001000000000000
Representao em Preciso nica
Exemplo: -5.125 5 101 (inteiro sem sinal) 0.125 0.100 5.125 101.100 22 x 1.01100 (normalizado) 2 2+127 = 129 10000001 (sistema de excesso) 1 10000001 011000000...
Representao em Preciso nica
Interpretao: Use o bit mais esquerda como sinal Converta os prximos 8 bits para decimal usando o
formato de excesso K = 127 Adicione 1. mantissa Mova o ponto at a posio correta, de acordo com o
expoente Converta a parte decimal Converta a parte real Combine as duas
Representao em Preciso nica
Ex: 10111110011001100000000000000000 Sinal: 1 - Expoente: 01111100 124 (-127) -3 Mantissa: 11001100... 1.11001100... -2-3 x 1.110011 -0.001110011 -0.224609375
Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53