Sistemas de Numeração Sistemas de Numeração Sistemas Po

Sistemas de Numeração
Os valores existem no mundo,
independentemente da sua representação
» WHAT WOULD LIFE BE WITHOUT
ARITHMETIC, BUT A SCENE OF
HORRORS? «
São representações
igualmente válidas
Sydney Smith, 1835
TC – DEI, 2004/2005
TC – DEI, 2004/2005
Sistemas Posicionais
Sistemas de Numeração
O sistema posicional é utilizado devido à
facilidade com a qual é possível fazer calculos
Tente encontrar um algoritmo para multiplicar, em
numeração romana, XVIII por XIXIII!
103 102 101 100
Paulo Marques
[email protected]
http://www.dei.uc.pt/~pmarques
Tecnologia dos Computadores 2004/2005
1 9 2 6
1926 = 1x103 + 9x102 + 2x101 + 6x100
TC – DEI, 2004/2005
Sistemas Posicionais (2)
Sistema de numeração de base 10:
Existem 10 algarismos diferentes
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
O valor de cada posição i é dado pelo valor
nessa posição vezes um factor de escala basei
Para calcular o valor de um número
representado numa base radix:
quatre-vingt,
quatre-vingt-dix,
quatre-vingt-dix-neuf
(An-1 An-2 An-3... A0)radix
80, 90, 99 em Françês
Faz-se:
An-1⋅radixn-1 + An-2⋅radixn-2 + An-3⋅radixn-3 + ... + A0⋅radix0
TC – DEI, 2004/2005
Nos sistemas informáticos
TC – DEI, 2004/2005
Contar em binário
Internamente, tudo é feito em base 2, i.e.
BINÁRIO
Existem dois símbolos: 0 e 1
(ligado/desligado, verdadeiro/falso)
Cada símbolo é um bit (binary digit)
No entanto, em termos de representações,
tipicamente utiliza-se:
Binário (base 2)
Hexadecimal (base 16)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
... e algumas vezes Octal (base 8)
TC – DEI, 2004/2005
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
(0)10
(1)10
(2)10
(3)10
(4)10
(5)10
(6)10
(7)10
(8)10
(9)10
(10)10
(11)10
(12)10
(13)10
(14)10
(15)10
TC – DEI, 2004/2005
Contar em hexadecimal
00
01
02
03
04
05
06
07
08
09
0A
0B
0C
0D
0E
0F
10
11
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
Nota
(0)10
(1)10
(2)10
(3)10
(4)10
(5)10
(6)10
(7)10
(8)10
(9)10
(10)10
(11)10
(12)10
(13)10
(14)10
(15)10
(16)10
(17)10
Virtualmente todos os informáticos sabem as
potências de dois de cabeça
210 29
28
27
26
25
24 23
1024 512 256 128 64 32 16
8
22
21
20
4
2
1
0
1
2
3
4
5
6
7
8
9
10
TC – DEI, 2004/2005
Quiz: Conversão para decimal
1
2
4
8
16
32
64
128
256
512
1024
TC – DEI, 2004/2005
Resposta ao Quiz
Converta para decimal os seguintes números:
Pista: lembre-se do que é que “sistema posicional” e
“base” querem dizer...
(1101010)2
(1101010)2
= 0⋅20 + 1⋅21 + 0⋅22 + 1⋅23 + 0⋅24 + 1⋅25 + 1⋅26
= 106 (na base 10)
(C1B3)16
= 3⋅160 + 11⋅161 + 1⋅162 + 12⋅163
= 49587 (na base 10)
(C1B3)16
TC – DEI, 2004/2005
TC – DEI, 2004/2005
Conversão de decimal para outras bases
Divide-se sucessivamente o número pela base
O resto da divisão vai constituindo os sucessivos
digitos do número
Exemplo: Converter 402 em binário
402 ÷ 2
201 ÷ 2
100 ÷ 2
50 ÷ 2
25 ÷ 2
12 ÷ 2
6÷2
3÷2
1÷2
= 201 e resto 0
= 100 e resto 1
= 50 e resto 0
= 25 e resto 0
= 12 e resto 1
=
6 e resto 0
=
3 e resto 0
=
1 e resto 1
=
0 e resto 1
Conversão binário-hexadecimal e vice-versa
Como 16 é 24, isso quer dizer que cada digito
em hexadecimal corresponde a 4 dígitos em
binário, directamente!
Exemplo: (110110010010)2
(402)10 = (110010010)2
TC – DEI, 2004/2005
Conversão decimal-hexadecimal
Exactamente o mesmo processo!
TC – DEI, 2004/2005
Nota sobre o sistema hexadecimal
Nos computadores (e livros), é comum utilizar
as seguintes notações para representar
números hexadecimais:
Converter 402 em hexadecimal
Converter 673 em hexadecimal
0xD92
D92h
402 ÷ 16 = 25 e resto 2
25 ÷ 16 = 1 e resto 9
1 ÷ 16 = 0 e resto 1
(402)10 = (192)16
673 ÷ 16 = 42 e resto 1
42 ÷ 16 = 2 e resto 10 (A)
2 ÷ 16 = 0 e resto 2
(673)10 = (2A1)16
TC – DEI, 2004/2005
ou
ou
0xd92
d92h
TC – DEI, 2004/2005
BCD: Binary-Coded-Decimal
Grandezas de armazenamento de informação
Nos sistemas electrónicos e muitas vezes nos
informáticos, utiliza-se também o sistema BCD:
Binary Coded Decimal
Cada conjunto de quatro bits representa um
valor decimal. Só são válidos os valores de
0000 a 1001 (i.e. 0 a 9)
BCD
Decimal
bit: binary digit, unidade básica de informação
byte: 8 bits
Kbyte: 210 byte, i.e. 1024 bytes
Mbyte: 210 Kbyte, i.e. 1024 Kbytes
Gbyte: 210 Mbyte, i.e. 1024 Mbytes
Tbyte: 210 Gbyte, i.e. 1024 Gbytes
Quiz: Se eu quiser armazenar 20.000.000
números inteiros, cada número de 32 bits,
quantos MByte preciso?
TC – DEI, 2004/2005
Armazenamento de dados
TC – DEI, 2004/2005
Grandeza para transmição de informação
Quantos bits são necessários para representar
N números?
Exemplo: quantos bits necessito para representar
100 objectos, ou para representar 100 números
diferentes? (0..99)
Sistema binário é um sistema posicional. Com
K bits, tenho 2K números diferentes
Para representar N elementos diferentes, são
necessários ⎡log2(N)⎤ bits.
Para representar 100 objectos, são necessários 7
bits!
TC – DEI, 2004/2005
Largura-de-banda:
100Mbps
100Mbps = 100*1000*1000 bits/s =
= 11.9 Mbyte/s
Note-se que no caso de bps, K, M, G e T
representam factores de 1000, não de 1024!
TC – DEI, 2004/2005
Palavras do computador
Máquinas big-endian & little-endian
Os registos do processador têm um certo tamanho em
bits. Ao tamanho dos registos do processador chamase word ou palavra.
Quando se diz que o Pentium 4 é um processador de 32 bits,
quer dizer que este manipula internamente dados de 32 bits.
Tipicamente também quer dizer que é capaz de gerar
endereços de 32 bits.
Imaginemos que um computador tem uma
palavra de 16 bits.
De que forma é que esta deverá ser armazenada
em memória?
MOV [1000], 0xff00
Quiz 1: Sabendo que o Pentium 4 endereça a memória
usando 32 bits, qual é a memória máxima que um PC
comum pode ter?
4 Gbytes! (232/1024/1024/1024)
Quiz 2: Sabendo que os registos de dados do Pentium
4 são de 32 bits, qual é o número máximo (sem sinal),
que se pode representar?
4294967295
(232-1)
TC – DEI, 2004/2005
1001
1000
ff
00
Little-endian
(e.g. PC)
1001
1000
00
ff
Big-endian
(e.g. Sun-Sparc, Network-byte-order)
TC – DEI, 2004/2005
Bit mais significativo e menos significativo
MSB
(Most Significant Bit)
LSB
(Least Significant Bit)
TC – DEI, 2004/2005
TC – DEI, 2004/2005
» Numbers written on restaurant bills
within the confines of restaurants do
not follow the same mathematical laws
as numbers written on any other pieces
of paper in any other parts of the
Douglas Adams, The Hitchhiker's Guide to the Galaxy
Universe «
» Every passing minute is another
chance to turn it all around. «
Sofia, in Vanilla Sky
TC – DEI, 2004/2005
TC – DEI, 2004/2005
Leitura... ☺
Representação de Números
Negativos & Racionais
−
Operações Aritméticas
The Ultimate
Hitchhiker's Guide to
the Galaxy
by Douglas Adams
ISBN 0345453743, Del Rey Publisher
The Hitchhiker’s Guide to the
Galaxy
The Restaurant at the End of
the Universe
Life, the Universe and
Everything
So Long, and Thanks for All
the Fish
Mostly Harmless
Paulo Marques
[email protected]
http://www.dei.uc.pt/~pmarques
Tecnologia dos Computadores 2004/2005
TC – DEI, 2004/2005
Números negativos: Sinal e Magnitude
Complementos para 1
O número negativo é obtido negando todos os bits do
correspondente positivo
Vantagens: muito fácil fazer cálculos e não é necessário processar o
bit de sinal separadamente
Quando se coloca um símbolo extra (+-) que
representa o sinal de um número, chama-se a
essa representação:
Representação em sinal e magnitude
(100)10 = (1100100)2
0 1 1 0 0 1 0 0
+100
1 1 1 0 0 1 0 0
-100
Bit Sinal
Magnitude
TC – DEI, 2004/2005
Números Negativos: Sistema de Complementos
Problemas do sistema de sinal e magnitude
Para fazer cálculos, as regras são confusas e
complicadas de implementar (e.g. se ambos os
sinais são positivos, o sinal é o mesmo, se um é
positivo e outro negativo, subtrai-se e o sinal é o do
maior em valor absoluto, etc.)
Existem duas representações para 0
+7
+6
+5
+4
+3
+2
+1
0
0
-1
-2
-3
-4
-5
-6
-7
0111
0110
0101
0100
0011
0010
0001
0000
1111
1110
1101
1100
1011
1010
1001
1000
Exemplo:
Somar 2 com -5
Subtrair a 2, o número 5
+
A ideia é simplificar as regras e os cálculos. Por
exemplo, subtrair deve de ser a mesma coisa do
que adicionar, e.g. 3 - 2 = 3 + (-2)
TC – DEI, 2004/2005
(+2)
1 0 1 0
(-5)
1 1 0 0
(-3)
TC – DEI, 2004/2005
Complementos para 1
Na verdade, fazer a adição é um pouco mais
complicado
+
0 1 0 1
(+5)
1 1 0 1
(-2)
Carry-out 1 0 0 1 0
1
0 0 1 1
Sistemas de complemento:
0 0 1 0
(+3)
Note-se que isto só se aplica quando são
números de sinais diferentes:
• O carry-out tem de ser adicionado!
As condições de overflow são algo
complicadas de detectar...
• Por exemplo, 5+5 = ??
TC – DEI, 2004/2005
Complementos para 2 − Overflow
Complementos para 2
O sistema utilizado em todas as máquinas modernas
Não é necessário uma pessoa preocupar-se com o carry
Cálculos realmente directos
Overflow é trivial de detectar
Uma única representação para o 0!
Conversão para complementos de 2 (dois métodos):
Calcula-se o complementos para um e soma-se 1
Copiam-se os bits da direita (LSB) para a esquerda até
encontrar o primeiro 1 e trocam-se todos os bits a partir dai.
Quando o resultado não cabe no número de
bits do resultado, diz-se que ocorreu um
overflow.
Na adição em complementos para dois, um
overflow é detectado quando o valor de carry
que entra no bit de sinal é diferente do que sai.
≠, o que implica que o cálculo está errado!
(23)10 = (00010111)2
Carry
(-23)10 = (11101001)2
(9)10 = (00001001)2
0 1 0 0
+
(-9)10 = (11110111)2
0 1 0 1
(+5)
0 1 1 0
(+6)
1 0 1 1
(-5) ????
TC – DEI, 2004/2005
Complementos para 2
+7
+6
+5
+4
+3
+2
+1
0
-1
-2
-3
-4
-5
-6
-7
-8
0111
0110
0101
0100
0011
0010
0001
0000
1111
1110
1101
1100
1011
1010
1001
1000
Representação de números reais
Existem dois sistemas de uso comum:
Exemplo:
Vírgula fixa: existe um determinado número de bits
fixo que representa a parte inteira, e um fixo de bits
que representa a parte fraccionária
Subtrair a 2, ao número 5
Somar 5 com -2
0 1 0 1
(+5)
1 1 1 0
(-2)
Carry-out 1 0 0 1 1
(+3)
+
TC – DEI, 2004/2005
3252.2153
Ignora-se o valor de carry!
1101.0001
103 102 101 100
10-1 10-2 10-3 10-4
3 2 5 2
2 1 53
23 22 21 20
2-1 2-2 2-3 2-4
1 1 0 1
0 0 01
• Quanto vale este número em decimal?
• Qual é o valor máximo e mínimo que
consigo representar?
TC – DEI, 2004/2005
TC – DEI, 2004/2005
Representação de números reais
Vírgula flutuante: o equivalente à
representação científica. Existe um número de
bits que corresponde a mantissa e um certo
número de bits que corresponde ao expoente
+3.4e+05
)
(=3.4x10+05
S 103 102 101 100
10-1 10-2 10-3 10-4
S 101 100
0 0 0 0 3
4 0 00
0 05
Mantissa
Algumas Operações
Importantes em Binário
Paulo Marques
[email protected]
http://www.dei.uc.pt/~pmarques
Expoente
Tecnologia dos Computadores 2004/2005
TC – DEI, 2004/2005
Formato IEEE 754
AND, OR, XOR
Actualmente virtualmente todos os
computadores utilizam o formato IEEE 754.
A base é implicita e é 2.
Precisão simples: 32 bits
É utilizado um código de excesso para a mantissa (127)
1bit
23 bits
8 bits
S
Mantissa
Expoente
Precisão dupla: 64 bits
É utilizado um código de excesso para a mantissa (1023)
1bit
52 bits
11 bits
S
Mantissa
Expoente
TC – DEI, 2004/2005
TC – DEI, 2004/2005
Operações Bitwise
01101
AND 01011
01001
01101
OR 01011
01111
Operações de Deslocamento (2)
01101
XOR 01011
00110
AND, útil para desligar bits!
Normalmente existem duas operações de
deslocamento à direita:
Lógica, em que é um deslocamento simples e o bit
que é introduzido no MSB é 0
1 1 0 1 1 0
Queremos desligar o terceiro bit de uma palavra:
01011110 AND 11111011 = 01011010
>> 1
0 1 1 0 1 1
Aritmética, em que o bit que é introduzido no MSB é
igual ao bit de sinal
OR, útil para ligar bits!
Queremos desligar o primeiro bit de uma palavra:
01011110 OR 00000001 = 01011111
Usado quando o deslocamento corresponde a uma divisão
e tem de se manter o valor do bit de sinal para as coisas
baterem certo!
XOR, útil para inverter bits!
Queremos trocar o primeiro bit de uma palavra:
01011110 XOR 00000001 = 01011111
01011111 XOR 00000001 = 01011110
1 1 0 1 1 1
TC – DEI, 2004/2005
Operações de Deslocamento
>>> 1
1 1 1 0 1 1
(-7)
TC – DEI, 2004/2005
That’s it!
Shift Right (SHR ou >>):
Desloca para a direita os bits de uma palavra
01011110 >> 2 = 00010111
Shift Left (SHL ou <<):
Desloca para a esquerda os bits de uma palavra
01011110 << 2 = 01111000
São operações importantes nomeadamente porque:
SHL 1: Corresponde a multiplicar o número por 2
SHL 2: Corresponde a multiplicar o número por 4
etc.
SHR 1: Corresponde a dividir o número por 2
SHR 2: Corresponde a dividir o número por 4
etc.
TC – DEI, 2004/2005
Sistema pictográfico de representar números... em chinês!
http://www.webcom.com/ocrat/chargif/numbers.html
TC – DEI, 2004/2005
Para saber mais...
[CSO] Computer Science – An Overview
Capítulo 1 (1.1, 1.2, 1.4-“representing numberic
values”, 1.5, 1.6, 1.7,
Capítulo 2 (2.4)
The Essentials of
Computer Organization and Architecture
Capítulo 2 (2.1 a 2.6.1);
cópias fornecidas no quiosque
TC – DEI, 2004/2005