September 09, 2013
Okay, para entender multiplicação em binário é necessário primeiro entender adição e subtração em binário, e sobre isso eu já escrevi no post anterior. Se você tem duvidas sobre esse assunto, recomendo ler e entender sobre isso antes de mergulhar aqui.
Primeiro vale definir que aqui usaremos 10 bits, como os dez dedos das mãos e daremos a esses bits os nomes de Bit1, Bt2, até Bit10, sendo o Bit1 o bit mais à direita, e o Bit10 o mais à esquerda. O Bit1 terá o valor de 1, o Bit2 terá valor 2, o Bit3 terá valor 4, e assim por diante, dobrando o valor, até que o Bit10 terá o valor 512. Todos os bits levantados somarão o valor 1023, todos os bits baixados = 0.
BIT10 BIT9 BIT8 BIT7 BIT6 BIT5 BIT4 BIT3 BIT2 BIT1
512 256 128 64 32 16 8 4 2 1
Para iniciar, vou rever aqui com vocês como se faz uma multiplicação tradicional em decimal no papel e lápis.
Vamos multiplicar 25 x 76
2 5
7 6
– - Multiplica-se Cruzado
3 0 = Cinco vezes Seis
3 5 - = Cinco vezes Sete
1 2 - = Dois vezes Seis
1 4 - - = Dois vezes Sete
– - - - Soma-se os resultados individuais
1 9 0 0 Resultado
Okay, explicarei de outra maneira.
Veja, em decimal os numeros vão de zero a 9, portanto para a mesma posição (digito) podem ocorrer dez variações do valor. Eu quero dizer que ao ter o número 35, para a mesma posição do “5″ pode-se ter de 30 a 39, portanto dez variações no dígito das unidades.
Em binário não é assim, é mais simples, pois binário só entender ZERO e UM, portanto para cada posição de bit, só teremos duas possíveis variações de valor. O binário ”10″ (2 em decimal) pode variar o bit mais a direita entre zero e um, portanto a “outra” combinação seria “11″ (3 em decimal) e só.
Então vejamos a outra maneira de multiplicar em decimal que imediatamente vai fazer você entender a multiplicação em binário.
325 x 76 (em decimal)
Okay, sem multiplicar, só somando. Primeiro vamos somar 5 vezes o número 76, e depois 2 vezes o número 760, e 3 vezes 7600. Mas de onde vieram o zero do 760 e os dois zeros do 7600? vieram do Vinte e do Trezentos, olhe bem, 325 é Trezentos + Vinte + Cinco. Deslocar o 76 uma vez para a esquerda e transforma-lo em 760 e soma-lo 2 vezes, é o mesmo que somar vinte vezes o 76.
Uma outra forma de entender é pensar assim: Trezentos e Vinte e Cinco é 300 + 20 + 5. Observe os zeros do trezentos e o zero do vinte.
Tanto faz multiplicar 325 x 76, ou (300 x 76) + (20 x 76) + (5 x 76), certo?
e também é o mesmo que passar os zeros para o 76, e ficaria assim:
(3 x 7600) + (2 x 760) + (5 x 76), correto?
Então seria assim:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
76 76 76 76 76 + 760 760 + 7600 7600 7600 ----- 24700 |
Percebeu que eu sempre uso o valor “76″ para as unidades (5), “760″ para as dezenas (2), e “7699″ para as centenas (3)?
Ai está o truque da multiplicação em binário. Acima, em decimal, terá que somar tantas vezes quanto for o número da unidade, dezena, centena, milhar, etc, e pode ir de zero a nove. Em binário só existem duas combinações, zero e um. Portanto, se for zero não soma, se for um soma e pronto, acabou para aquela posição de bit. Abaixo entenderá com mais detalhes.
Treze em decimal é 0x0D em hexadecimal, ou 0b1101 em binário
Cinco em decimal é 0×05 em hexadecimal, ou 0b0101 em binário
Então vamos multiplicar 0x0D x 0×05
|
1 |
1 1 0 1 x 0 1 0 1 |
Assim como na multiplicação em decimal, note que as multiplicações individuais do cruzado se deslocam para a esquerda sempre que se multiplica um digito que está mais para a esquerda, na verdade se escreve o resultado da multiplicação exatamente na mesma coluna que se está multiplicando.
No processo binário é muito parecido, porém se desloca toda a linha superior ao observar cada bit da linha inferior, e se esse bit da linha inferior for um (1) soma-se a linha superior ao resultado, caso seja zero, continua-se movendo a linha superior para a esquerda até acabarem os bits da linha inferior.
Lembre-se de passar os zeros do 300 e do 20 para o 76, aqui abaixo é o mesmo, conforme vamos tirando bits do multiplicador (vemelho), estamos enfiando zeros na Linha Superior (azul).
Veja:
[raw]
| Linha Superior | Multiplicador |
| - – - – 1 1 0 1 | 0 1 0 1 |
| Olhe o ultimo bit à direita do Multiplicador acima (em vermelho), se for um (1), soma-se a Linha Superior ao Resultado. Desloca-se a linha superior uma posição para à esquerda, enfia-se um zero à direita, desloca-se o Multiplicador (acima) um bit à direita, ou seja, elimina-se o bit mais à direita do Multiplicador. Nesse caso, o ultimo bit à direita do Multiplicador acima é “1″, então os bits da Linha Superior “1101″ são adicionados ao Resultado. | |
| - – - 1 1 0 1 0 | 0 1 0 |
| Olhe o ultimo bit à direita do Multiplicador acima (em vermelho), como é zero (0), os bits da Linha Superior “11010″ não será adicionado ao Resultado. Porém a Linha Superior será deslocada um bit à esquerda, e o ultimo bit to Multiplicador (acima em vermelho) será eliminado. | |
| - – 1 1 0 1 0 0 | 0 1 |
| Olhe o ultimo bit à direita do Multiplicador acima (em vermelho), como é um (1), os bits da Linha Superior “110100″ (com os dois ultimos bits em azul) serão adicionados ao Resultado. Então a Linha Superior será deslocada um bit à esquerda, e o ultimo bit to Multiplicador (acima em vermelho) será eliminado. | |
| - 1 1 0 1 0 0 0 | 0 |
| Olhe o ultimo bit à direita do Multiplicador acima (em vermelho), como é zero (0), nada será adicionado ao Resultado, e como ele é o último bit do Multiplicador, a operação está encerrada e o Resultado é o valor da multiplicação entre a Linha Superior e o Multiplicador. | |
| - – - – 1 1 0 1 | À esquerda as somas ao Resultado das quatro operações acima. Os bits (1) do Resultado são 1 e 64, que somados formam 65 em decimal, portanto está correta a multiplicação. |
| - – - 0 0 0 0 0 | |
| - – 1 1 0 1 0 0 | |
| - 0 0 0 0 0 0 0 | |
| - – - – - – - – - | |
| - 0 1 0 0 0 0 1 |
[/raw]
Percebeu como é simples e fácil?
Basta ir olhando para os bits da linha inferior. Para cada bit que você olha mais para a esquerda, enfia um zero ao final da linha superior. Se o bit que olhou na linha inferior é 1, some a linha superior no resultado. É só isso.
Ao fazer isso em Assembly, usa-se deslocar para a direita a linha de baixo, se ocorreu “carry bit”, ou seja, o bit mais à direita da linha de baixo era “1″, e o carry bit é “1″, então soma-se a linha superior ao registrador do resultado. Se o bit mais à direita da linha de baixo era “0″ e agora o carry bit é zero então não se soma nada ao resultado. Então shifta-se toda a linha superior um bit à esquerda, independente dela ter sido somada ao resultado ou não. Repete-se essa sequência até a linha de baixo só ter zeros.
Pronto, o registrador de resultados já terá o valor da multiplicação. Veja que essa técnica funciona para qualquer quantiadade de bits ou bytes, basta ter espaço para shiftar para a esquerda a linha superior e ter espaço no registrador de resultados para ir fazendo as somas.