MULTIPLICAÇÃO EM BINÁRIO - 2

Multiplicação em Binário, Tipo 2

Já expliquei em outro post como multiplicar em binário, mas agora explico uma nova maneira de multiplicar, que talvez seja até mais simples de entender e fazer, apesar de ser sempre a mesma coisa, ter a mesma base, e usar a mesma mecânica.  Como curiosidade, essa técnica de multiplicar foi usada por fazendeiros russos há séculos, e se adapta perfeitamente à computadores.

Consideremos que a nossa multiplicação tenha dois operadores, A e B.

Vamos assumir A=1537 e B=723

O resultado esperado será 1527 x 723 = 1104021

Usaremos uma variável R como sendo o resultado.

   1) R=0

   2) Shift A um bit para a direita (dividindo por 2)

   3) Se ocorreu carry bit, ou seja, A “era” impar, some B em R

   4) Shift B um bit para a esquerda

   5) Repita 2-4 até A ser zero.

Pronto, R contém o resultado de A x B

A técnica é somar o valor atual de B em R, só quando A for impar, e desprezar B quando A é par.

Duvida? Veja:

                   A                         B                         R

1 2 3 4 5 6 7 8 9 10 11 12 13

1527       723        723 + 763      1446       1446 + 381      2892       2892 + 190      5784          0 (A:par, ignore)   95     11568      11568 +   47     23136      23136 +   23     46272      46272 +   11     92544      92544 +    5    185088     185088 +    2    370176          0 (A:par, ignore)    1    740352     740352 +    0         0          0                   1104021 <== Total da soma em R

Isso é muito simples, não é?  Escrever isso em software é ainda mais simples, só usa shift right em A, shift left em B e soma de B em R quando o menor bit de A estiver levantado (impar), nada mais.  

A quantidade de shifts será "n", onde "n" é a potência de 2 (2^n) do valor de A (o maior).  Por exemplo, o valor 1527 tem o próximo maior binário 2048 que é representado por 2^11. Observe que o exemplo acima usa exatamente 11 passos.