Você dispõe de dez moedas, todas diferentes, a menor valendo $i$ 1,00 (unidade monetária de $i$temas de Informação), a segunda $i$ 2,00, a terceira $i$ 4,00, e assim por diante, cada uma valendo o dobro da imediatamente anterior. Neste caso, a moeda de maior valor é a de $i$ _____,00. Se você precisasse pagar uma dívida de $i$ 313,00 , que moedas usaria?
Suponha a seguinte sequência de valores ordenados da direita para a esquerda e marque, na linha abaixo, o padrão indicador das moedas que serão utilizadas (1 para 'USADA' e 0 para 'NÃO-USADA');
512 256 128 064 032 016 008 004 002 001
___ ___ ___ ___ ___ ___ ___ ___ ___ ___
E se você precisasse pagar uma dívida de $i$ 626,00 , isto é, o dobro de $i$ 313,00 , que moedas usaria? Marque o padrão indicador das moedas que serão utilizadas (1 para 'USADA' e 0 para 'NÃO-USADA');
512 256 128 064 032 016 008 004 002 001
___ ___ ___ ___ ___ ___ ___ ___ ___ ___
Que semelhança tem o primeiro padrão (que representa 313) com o segundo (que representa 626, ou 2 x 313)?
Para certos valores altos, escolher as moedas por inspeção direta pode ser complicado. Contudo, através de divisões e multiplicações por dois, encontrar a composição adequada de moedas é, de fato, bem fácil. Os egípcios utilizavam métodos 'binários' semelhantes a esses em operações aritméticas, pelo menos há quatro mil anos, algo documentado no assim chamado Papiro de Ahmes, ou de Rhind (cerca de 1650 AC). Também estão descritas multiplicações 'binárias' usadas até recentemente por comunidades (atualmente) ágrafas do norte da África para o comércio cotidiano ('Multiplicação da Etiópia), e o método é também conhecido como 'Multiplicação Russa', por ter sido muito praticado por camponeses russos antes da revolução de 1917 (ver, por exemplo, C.S.Ogilvy & J.T.Anderson, 'Excursions in Number Theory', pg.6; ou G.Flegg, 'Numbers, Their History and Meaning', pg.90-91).
A idéia é substituir o problema de representar um número grande (difícil) pelo de representar a sua metade (mais fácil) multiplicada por dois (fácil). No caso de o número grande ser ímpar, devemos acrescentar uma unidade à representação. Para representar 13, por exemplo, basta representar o dobro de SEIS e acrescentar 1.
Se conhecemos a representação binária de DOZE, é imediato encontrar a representação binária de TREZE, sucessor de DOZE. Mas, ainda sem conhecer a conversão binária de DOZE, sabemos sobre o DOZE que é o DOBRO DE SEIS. Saber que DOZE é o DOBRO DE SEIS é importante porque representar em binário o dobro de um padrão binário é imediato, bastando deslocar o padrão para a esquerda. Assim,
[DOZE]=[DOBRO DE SEIS]. Supondo que
[SEIS]=[? ? ? ?] em binário, então o
[DOBRO DE SEIS]= [? ? ? ? 0] em binário=[DOZE]. O zero ao final da representação [? ? ? ? 0] em binário significa que deslocamos o padrão [? ? ? ?] uma casa para a esquerda, o que equivale, em binário, a multiplicar o padrão por 2.
Dito de outro modo, [DOZE] é o padrão binário correspondente ao [SEIS] com um zero acrescentado à direita, de modo a deslocar o padrão [SEIS] uma casa binária para a esquerda.
E o [DOBRO DE SEIS] + 1 = [? ? ? ? 0] + 1 = [? ? ? ? 1] em binário = [TREZE].
De modo análogo, mesmo sem saber a conversão binária de [SEIS], sabemos que
[SEIS]=[DOBRO DE TRÊS]. Supondo que
[TRÊS]=[? ? ?] em binário, então o
[DOBRO DE TRÊS]= [? ? ? 0] em binário.
Isto é, [SEIS] é o padrão binário correspondente ao [TRÊS] com um zero acrescentado à direita, de modo a deslocar o padrão [TRÊS] uma casa para a esquerda.
Já podemos escrever que o
(DOBRO do [DOBRO DE TRÊS]) + 1 = ([? ? ? 0] 0) + 1 = [? ? ? 0 1] em binário = [TREZE]
De modo análogo, mesmo sem saber a conversão binária de [TRÊS], sabemos que
[TRÊS]=[DOBRO DE UM] + 1. Sabemos que [UM] em binário se escreve como 1, e que
[TRÊS]= 1 0 + 1 em binário = 1 1 em binário.
Logo,
[SEIS] = 1 1 0 em binário,
[DOZE] = 1 1 0 0 em binário, e
[TREZE]= 1 1 0 1 em binário.
Recapitulando o que fizemos, para representar 13 decimal em binário,
13 = [2 x 6] + 1 = [6]0 binário + 1 = [6]1, seja qual for a conversão de [6]
6 = [2 x 3] = [3]0 binário, logo
[6]1= [3]01, seja qual for a conversão de [3]
3 = [2 x 1] + 1 = 10 + 1, logo
[3]01 = 1101
Resumindo, em uma notação mais abreviada,
[13]=[6]1=[3]01=1101
Encontre a representação binária de 23 (decimal):
[23]=[11]1=[5]11=[2]111=10111
Voltando ao exemplo inicial, pagar $i$ 313,00 é o mesmo que pagar duas vezes $i$ 156,00 mais $i$ 1,00. Se conhecêssemos o 'padrão' de moedas que paga $i$ 156,00, bastaria deslocá-lo para a esquerda (isto é, multiplicá-lo por dois, obtendo $i$ 312,00) e, além disso, marcar a moeda de $i$ 1,00 (para completar $i$ 313,00)
Se não conhecemos o padrão representativo de $i$ 156,00, podemos repetir o mesmo processo até atingir uma representação conhecida. Assim, 156 corresponde ao dobro de 78, que é, por sua vez, o dobro de 39. Se soubermos que padrão representa 39, basta deslocá-lo para a esquerda, e teremos o padrão representativo de 78. Repetindo o processo, obtemos o padrão para 156 e, voltando a deslocar esta composição para a esquerda, obtemos a representação de 312.
'Substituir' um valor pelo 'dobro da metade' implica, então, acrescentar uma posição imediatamente à direita do padrão binário que representa aquela metade; se o valor original for ímpar, aquela posição deve conter 1 e, se for par, conterá 0.
Cada posição binária sinaliza 0 ou 1, conforme o resto das divisões sucessivas por 2 que sofre o valor original.
313 =[312+1]=[156x2+1]
[156]1=[78x2]1=
[78]01=[39x2]01
[39]001=[38+1]001=[19x2+1]001
[19]1001=[18+1]1001=[9x2+1]1001
[9]11001=[8+1]11001=[4x2+1]11001
[4]111001=[2x2]111001=
[2]0111001=[1x2]0111001=
[1]00111001
313d = 100111001b
Represente 107 (decimal) em binário:
107 =[106+1]=[53x2+1]
...
107d = 1101011b