20 Dezembro 2007

Multiplicação em binário.

Imaginemos uma simples multiplicação entre dois números decimais: 7 . 5 = 35

Em binário:

x2 = 111 (710)
y2 = 101 (510),
ou seja: y10 = 1 . 22 + 0 . 21 + 1 . 20 ou 1 . 1002 + 0 . 102 + 1 . 12

se,

y = 1 . 100 + 0 . 10 + 1 . 1 = 101

então

111 . 101 = 111 . (1 . 100 + 0 . 010 + 1 . 001)

De acordo com a propriedade distributiva:

111 . (1 . 100) + 111 . (0 . 010) + 111 . (1 . 001)

Fazendo uso das propriedades associativa e comutativa:

111 . 101 = (111 . 100) . 1 + (111 . 10) . 0 + (111 . 1) . 1

Este trabalho todo para decompor o multiplicador nos seus bits e aplicar essa decomposição à operação serve para garantir que a multiplicações sejam sempre feitas com resultados a expoenciação da base 2.

(101 = 1 . 100 + 0 . 10 + 1 . 1)

Em qualquer base numérica, multiplicar um numero pela base ou por resultados da expoenciação da base é equivalente a “deslocar” o numero para a esquerda (adicionando zeros) ex.: 310 . 1010 = 3010

donde:

111 . 100 = 11100
111 . 10 = 1110
111 . 1 = 111


assim:

111 . 101 = 11100 . 1 + 1110 . 0 + 111 . 1
= 11100 + 0 + 111
= 100011
= 3510

Consegue-se resumir a operação de multiplicação, que não existe na maior parte dos microprocessadores ou microcontroladores de 8 bits, nas operações de soma e deslocar (shift).

Podemos então escrever o seguinte algoritmo:

; operação de multiplicação z = x . y
z = 0
enquanto y != 0
o bit menos significativo de y == 1?
sim: z = z + x
x << 1
y >> 1

Sem comentários: