A matemática simples atrás de algoritmos de conversão decimal-binário

Se procurar na web por “Como converter de decimal para binário” encontrará quatro algoritmos simples: dois para o número inteiro e dois para as fracções. São apresentados com exemplos abaixo na primeira parte do artigo. Mas embora apenas conhecer os algoritmos seja quase sempre suficiente, decidi tentar compreender porque é que eles funcionam. Na segunda parte, este artigo explica a matemática muito básica por detrás de cada um deles. Conhecê-la pode ajudá-lo a lembrar-se de qualquer um dos algoritmos se de repente os esquecer. Aqui estão os quatro algoritmos com exemplos que pode encontrar na web.

Converter o inteiro decimal para binárioLink para esta secção

Para converter o inteiro para binário, comece com o inteiro em questão e divida por 2 mantendo o aviso do quociente e o restante. Continuar a dividir o quociente por 2 até obter um quociente de zero. Depois basta escrever os restantes na ordem inversa.

Aqui está um exemplo de tal conversão usando o inteiro 12.
Primeiro, vamos dividir o número por dois especificando o quociente e o restante:

Agora, precisamos simplesmente de escrever o restante na ordem inversa -1100. Assim, 12 em sistema decimal é representado como 1100 em binário.

Convertendo a fracção decimal para binárioLink para esta secção

Para converter a fracção em binário, começar com a fracção em questão e multiplicá-la por 2 mantendo a observação da parte inteira e fracção resultante. Continuar a multiplicar por 2 até obter uma parte fracionária resultante igual a zero. Depois basta escrever o inteiro a partir dos resultados de cada multiplicação.

Aqui está um exemplo de tal conversão usando a fracção 0.375.

Agora, vamos apenas escrever a parte inteira resultante em cada passo – 0.011. Assim, 0,375 em sistema decimal é representado como 0,011 em binário.

Converter o inteiro binário para decimalLink para esta secção

Para converter o inteiro binário para decimal, comece a partir da esquerda. Pegue no seu total actual, multiplique por dois e adicione o dígito actual. Continue até não haver mais dígitos. Aqui está um exemplo de tal conversão usando a fracção 1011.

Convertendo o inteiro da fracção decimal para esta secção

Para converter a fracção binária para decimal, comece pela direita com o total de 0. Pegue no seu total actual, adicione o dígito actual e divida o resultado por 2. Continue até já não haver mais dígitos. Aqui está um exemplo de tal conversão usando a fracção 0,1011. Substituí simplesmente a divisão por 2 com multiplicação por 1/2.

Há 4 algoritmos simples que lhe permitirão converter números binários para decimal e para trás.

Base-q expansão de um númeroLink para esta secção

A chave para compreender porque é que esses algoritmos funcionam é um base-q expansion de um número. Um número inteiro em qualquer sistema numérico pode ser representado da seguinte forma:

onde,

N é o número inteiro
x é o dígito (0 a 9 para sistema base-10, 0 e 1 para sistema base-2)
q é o valor base (10 para sistema base-10, 2 para sistema base-2)

Através deste artigo este formulário é referido como base q expansion of the number N, ou simplesmente base q expansion. Vejamos como procura o número 12 nos sistemas decimal e binário:

Likewise, um número fracionário em qualquer sistema numérico pode ser representado na seguinte forma:

where,

N é uma fracção
x é o dígito (0 a 9 para sistema base-10, 0 e 1 para sistema base-2)
q é o valor base (10 para sistema base-10, 2 para sistema base-2)

Para o número 0.375 nos sistemas decimal e binário a representação é a seguinte:

Convertendo o inteiro decimal para binaryLink para esta secção

Como acontece, podemos usar esta forma de expansão base-q para converter um número do sistema decimal para o binário. Vamos fazer isso para o mesmo número 12. Primeiro, vamos fingir que não sabemos como é representado no binário e escrevê-lo com dígitos desconhecidos substituídos por x:

A nossa tarefa é encontrar todos os x’s. Vejamos o que podemos fazer aqui. A primeira coisa que temos de notar aqui é que todos os somatórios, excepto o último, serão números pares, porque todos eles são múltiplos de dois. Agora, utilizando esta informação podemos inferir o dígito para o x0 – se o inteiro a ser convertido for par, então x0 é igual a 0, se for ímpar – então x0 deve ser 1. Aqui temos o número 12 que é par, portanto x0 é zero. Vamos escrever esta informação:

Next, precisamos de encontrar o valor para o x1. Uma vez que todas as somas de x1 a xN são múltiplos de dois, podemos considerar 2 para destacar o x1. Vamos fazer isso:

É também fácil ver que a soma dos valores dentro dos parênteses é igual a 6. Assim, podemos escrever o nosso primeiro passo como:

p>Vamos continuar a descobrir os x’s restantes. Podemos escrever o polinómio dentro do parêntesis como uma declaração separada:

Haqui, aplicando a mesma lógica de cima, podemos ver que x1 é igual a 0. Vamos reescrevê-lo e também factor 2 novamente:

Portanto, o nosso segundo passo é:

Agora, podemos ver um padrão. Podemos continuar a factorar 2 até que o quociente seja zero. Vamos seguir este padrão e ver o que obtemos.

Desde que o quociente é igual a 1, resta apenas uma soma, por isso vamos reescrever a expressão anterior:

Portanto, o nosso terceiro passo é:

Então, acabamos com o seguinte:

É evidente que x3 é igual a 1. Mas, como para o nosso algoritmo precisamos de um quociente, vamos reescrever a expressão anterior para que tenha um quociente:

Desde que acabamos com o quociente 0, não há mais nada com que trabalhar e este foi o nosso último passo. Vamos escrevê-lo:

Então agora terminámos a conversão. Eis como fica a nossa conversão por passos:

É agora claro que o restante em cada passo corresponde ao valor de x nas posições correspondentes: o primeiro restante corresponde ao primeiro x, o segundo ao segundo x e assim por diante. Assim, o número 12 em binário utilizando o algoritmo descrito acima é representado como 1100,

Lembra-te que começámos com a ideia de mostrar porque é que o algoritmo que envolve o mergulho por 2 trabalhos. Vamos dar os passos descritos acima e mover o 2 para a parte esquerda das expressões:

Assim, desta forma podemos ver como chegámos ao algoritmo descrito no início. Podemos também colocar os cálculos para aqueles quatro passos numa representação como esta

Confirmeça-se de compreender como chegamos a essa representação, pois precisaremos dela ao explorar como funciona o algoritmo de conversão de binário para decimal.

Converter a fracção decimal para binárioLink para esta secção

Para mostrar porque é que multiplicamos por 2 e tomamos a parte inteira quando convertemos fracções para binário, também vou usar o formulário de expansão base-q para fracções. Vou usar o número fracionário 0,375 da primeira parte do artigo. Tal como na parte inteira, vamos fingir que não sabemos como este número é representado no binário e escrevê-lo com dígitos desconhecidos substituídos por x:

Como com números inteiros, a nossa tarefa é encontrar todos os x’s destacando os x’s. Vamos ver como podemos fazer isso. A primeira coisa a notar aqui é que os poderes negativos de 2 dão-nos fracções com o denominador de 2 com poderes positivos. Vamos reescrever a expressão acima:

É imediatamente óbvio que podemos simplesmente factorar 1/2 na parte direita da expressão. Vamos fazer isso:

e podemos então mover 1/2 para a parte esquerda

Okay, aqui escolhemos x1, e sabemos que pode ser ou 1 ou 0. Para determinar que dígito tem vamos dar uma vista de olhos aos restantes números:

P>Vamos pensar no quão grande pode ser a soma destes números. Se o número máximo de x dígitos for 1, então podemos simplesmente substituir x por 1 e escrever a soma como:

Bem, esta é uma série geométrica de fracções, e a soma de tais séries encontra-se nos limites, pelo que o número máximo que tal soma nos pode dar é 1. Vejamos agora novamente a nossa expressão:

Agora, isto deve ficar claro aqui que se o lado direito for inferior a 1, então x1 não pode ser igual a 1 e por isso é igual a 0, enquanto a parte restante é igual a 0,75.

Esta parece exactamente como o primeiro passo no algoritmo apresentado no início:

Vamos retirar a parte fracionária de 0.75 e factor out outro 1/2 para destacar x2:

e mover 1/2 para a esquerda:

Agora, se x2 for igual a 0, então a soma do lado esquerdo da expressão não pode ser superior a 1, mas o lado esquerdo é 1.5, pelo que x1 deve ser 1 e a parte restante 0,5. Vamos escrevê-lo:

Again, isto segue o padrão no algoritmo apresentado no início:

Vamos repetir as mesmas acções para a parte fracionária restante de 0.5.

Usando a mesma lógica que acima podemos ver que x3 é igual a 1 e não há nenhuma parte fracionária restante:

Desde que a parte fracionária restante seja igual a 0, é assim que se parece o nosso último passo:

Então vamos escrever novamente todos os passos:

Este é exactamente o algoritmo que apresentei no início. Tal como fizemos com os números inteiros, também podemos colocar os cálculos para esses três passos numa representação como esta:

a>a ganhar, é importante que se apreenda completamente esta representação, pois precisaremos dela ao explorar a conversão binária para decimal.

Porque nem todas as fracções podem ser finitamente representadas em ligação binária a esta secção

O facto de algumas fracções representadas finitamente em sistema decimal não poderem ser finitamente representadas em sistema binário é uma surpresa para muitos programadores. Mas esta é exactamente a confusão que reside na raiz do resultado aparentemente estranho de adicionar 0,1 a 0,2. Então, o que determina se uma fracção pode ser finitamente representada num sistema numérico? Bem, para que um número seja finitamente representado, o denominador numa fracção deve ser um poder da base do sistema. Por exemplo, para o sistema base-10, o denominador deve ser uma potência de 10, e é por isso que podemos representar finitamente 0.625 em decimal:

e não pode representar finitamente 1/3:

O mesmo se aplica ao sistema base-2:

Mas se verificarmos 0.1, o denominador é 10 e não é uma potência de 2, portanto 0,1 vai ser uma fracção infinita no sistema binário. Vamos vê-lo usando o algoritmo que aprendemos acima:

Podemos continuar a fazer isso infinitamente, mas vamos escrevê-lo como fracção contínua periódica:

Converter o número inteiro binário para decimalLink para esta secção

Vou usar o mesmo número inteiro binário 1011 da primeira secção para lhe mostrar porque é que o algoritmo de multiplicar por 2 funciona. Aqui também utilizaremos a forma de expansão base-q do número. Vamos escrevê-lo nesta forma:

Desde que todas as somas sejam múltiplos de 2, podemos manter o factor 2 até que o quociente seja zero. Vamos fazer isso:

Agora, se simplesmente seguir a ordem das operações matemáticas acabará com exactamente os mesmos passos que eu mostrei no início, particularmente:

Desta forma, 1011 em binário é 11 em decimal.

Converter a fracção binária para decimalLink para esta secção

Agora, chegámos ao último algoritmo. Provavelmente, já se descobriu a mecânica por detrás dele. Se não, vamos ver porque é que funciona. A forma de expansão base-q do número é também a chave aqui. Tomaremos o número 0,1011 da primeira secção. Vamos escrevê-lo na forma expandida: