Introdução
É muito comum precisarmos converter um número em uma base numérica para outra, principalmente quando a conversão envolve as bases 10, 2 e 16. Muitas linguagens de programação oferecem funções ou métodos para realizar essa tarefa de conversão, porém é sempre útil entendê-la e implementá-la manualmente.
Hoje veremos alguns algoritmos para converter bases numéricas.
O que é base numérica?
Uma base numérica é um conjunto finito de símbolos usados para representar quantidades numéricas. A base mais comum é a base 10, que nos fornece 10 símbolos para serem usados nessa representação. A conversão entre bases numéricas é a passagem de uma base para outra, ou seja, muda-se somente a representação simbólica, preservando o valor quantitativo.
Os símbolos usados nas bases numéricas são os algarismos arábicos que todos nós já conhecemos: 0, 1, 2, …, 9. Para bases maiores que 10, as letras do alfabeto também são usadas. Bases entre 11 e 26 usam as letras do alfabeto maiúsculo, e as bases acima de 26 utilizam também o alfabeto minúsculo. Observe que podemos trocar os algarismos arábicos por outros símbolos, inclusive strings, resultando naquele princípio de gerar permutações de strings, visto no post [2].
Um detalhe: base64
Base64 é um algoritmo utilizado, principalmente, para transformar dados binários em texto. Esse algoritmo não é simplesmente transformar para a base 64 como alguns devem pensar. Ele, na verdade, é um conjunto de padrões que visa mapear qualquer stream de bits nos 64 caracteres de textos mais usuais (isto é: [a-zA-Z0-9+/]). Veja mais sobre base64 em [3].
Convertendo da base n para a base m
A seguir veremos 3 procedimentos comuns para a conversão entre bases.
1) Processo de contagem
Todo mundo sabe que depois do “8” vem o “9” e depois do “9” vem o “10”. A disposição de todas permutações dos símbolos de uma base em uma ordem específica é o que denominamos de processo de contagem. Esse processo nada mais é que pegar a representação para a quantidade zero e avançar a quantidade em uma unidade e obter a representação equivalente.
Para a base 4, os primeiros 17 termos da contagem são:
0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33, 100, etc
Se fizermos o processo de contagem simultaneamente em outras bases, os termos na mesma posição representam a mesma quantidade, isto é:
Processo de contagem
Logo, podemos ver que 13(4), 7(10) e 111(2) representam a mesma quantidade, e assim, para converter, por exemplo, um numeral na base 4 para a base 2, basta olharmos os termos correspondentes.
Obviamente o processo de contagem não é muito viável, pois para números grandes teremos que gerar sequências enormes. Porém, esse método é muito útil para gerar permutações. Se trocarmos os símbolos 0, 1, 2 e 3 da base 4, por a, b, c e d, e considerando o zero à esquerda, teremos:
aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd, baa, etc
\___________________________ ________________________________/
v
Permutações dois a dois de a, b, c, d
O processo de contagem nada mais é que a permutação-r dos símbolos da bases. Esse conceito para gerar permutações já foi exemplificado em [2].
2) Método da expansão
Esse método utiliza a definição de um número em sua forma polinomial:
abcdef = a*(B^5) + b*(B^4) + c*(B^3) + d*(B^2) + e*(B^1) + f*(B^0) sendo B, a base atual do número abcdef.
A intuição disso é que um símbolo na posição d só é mudado quando os símbolos nas posições e e f alcançam o limite B de símbolos. Para um símbolo em e variar é necessário que o símbolo em f ultrapasse o limite B de símbolos, daí vem o e*B. O mesmo acontece em d, só que agora com um grau de dependência maior: para se mudar um símbolo em d, é necessário que o símbolo em e chegue ao limite B, porém para que cada símbolo em e seja mudado, é necessário que o símbolo em f chegue também ao limite B. Daí chegamos em d*B^2, pois para cada símbolo em e, um total de B símbolos em f foram usados, resultando em B^2. Esse processo se repete para as outras posições até que o resultado final do polinômio seja igual a quantidade de símbolos usados.
Exemplo:
111001(2) = (1*2^5 + 1*2^4 + 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0)(10)
= (32 + 16 + 8 + 0 + 0 + 1)(10)
= 57(10)
O resultado já saiu na base 10, porque resolvi as operações usando aritmética decimal. Se resolvermos essas operações em uma base m, o resultado final também estará na base m. Veja:
57(10) = (5*10^1 + 7*10^0)(10)
= (101*1010^1 + 111*1010^0)(2) <- símbolos da base 2
= (110010 + 111)(2)
= 111001(2) <- resultado na base 2
A desvantagem desse método de conversão é que ele exige que as operações matemáticas sejam feitas em cima da base destino. Se a base destino for a decimal, fica fácil a conversão, porém, para outras bases, o processo não parece muito intuitivo, como vimos no exemplo acima.
3) Método da divisão
Convertendo 13(10) para binário, obtemos a representação 1101(2). Para alcançar esse resultado, seguimos o procedimento: divida 13 por 2. Obtenha o quociente 6 e o resto 1. Continue esse processo, mas utilizando o último quociente como dividendo. Pare somente quando o quociente for zero. Os restos gerados, se anotados de forma contrária, nos darão a representação do 13(10) em binário.
13 / 2 = 6 resto 1 6 / 2 = 3 resto 0 3 / 2 = 1 resto 1 1 / 2 = 0 resto 1 Logo, 13(10) = 1101(2)
Veja que esse método funciona para qualquer base:
35(10) / 3 = 11 resto 2 11 / 3 = 3 resto 2 3 / 3 = 1 resto 0 1 / 3 = 0 resto 1 Logo: 35(10) = 1022(3)
Em ambos exemplos utilizei a base 10 como base fonte. O motivo disso é que a operação de divisão nessa base é muito mais intuitiva que em qualquer outra.
A prova que isso funciona é mostrada formalmente na referência [6]. Basicamente ela nos diz o seguinte: suponha Ai um inteiro, Ai+1 o quociente da divisão, ri o resto da divisão para algum i>=0 e t a base destino. Podemos escrever Ai como:
Ai = (Ai+1)*t + ri dividindo por t: (Ai)/t = Ai+1 + (ri)/t
Sendo A0 o inteiro que queremos converter e t a base destino. Pelo método da expansão, temos:
Prova método da divisão
Em seguida aplicamos em A1 o mesmo que fizemos em A0 e a cada iteração obteremos um resto ri = bi, onde bi é o símbolo na base t correspondente à posição i do resultado. A expansão e o restante da prova podem ser vistos na referência [6].
Base 10 como intermediária
Em geral, evitamos realizar operações com bases não muito usuais (ex: base 7). O ideal, então, é utilizar a base 10 sempre que possível em algum lugar no processo de conversão.
Isso é, para converter uma base n para uma base m, é sempre mais fácil fazer, primeiramente, a conversão da base n para base 10 pelo método da expansão, e em seguida transformar da base 10 para a base m pelo método da divisão.
1465(8) = (1*8^3 + 4*8^2 + 6*8^1 5*8^0)(10)
= (512 + 256 + 48 + 5)(10)
= 821(10)
= 821(10) / 3 = 273 resto 2
= 273 / 3 = 91 resto 0
= 91 / 3 = 30 resto 1
= 30 / 3 = 10 resto 0
= 10 / 3 = 3 resto 1
= 3 / 3 = 1 resto 0
= 1 / 3 = 0 resto 1
Logo, 1465(8) = 1010102(3)
Conversão de base no Linux
No Linux temos vários modos de se converter bases numéricas. Programas ou bult-ins como bc, dc, printf, $(()) podem ser usados para essa tarefa. Aqui no blog tem um bom material sobre isso na referência [7].
Implementação
Para finalizar o assunto discutido nesse post, colocarei um código em C implementando funções para o método da expansão e para o método da divisão.
/*
* [dbase.c]
* Converte um número da base N
* para a base M, indicadas como
* parâmetro.
*
* [Autor]
* Marcos Paulo Ferreira (daemonio)
* undefinido gmail com
* https://daemoniolabs.wordpress.com
*
* [Compilação]
* $ gcc -o dbase dbase.c
*
* [Uso]
* $ ./dbase <numero> <basen> <basem>
*
* ex:
* $ ./dbase 1100110101010 2 16
* 19AA
* $ ./dbase 19AA 16 2
* 1100110101010
* $ ./dbase EBACOCA 16 29
* C1BCLP
*
* [Observações]
* - Esse código deve ser usado somente para
* propósitos educacionais. Nenhuma checagem
* por erros foi feita para não aumentar o
* tamanho do código.
*
* Versão 1.0, by daemonio @ Wed Jul 18 16:08:38 BRT 2012
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *alfabeto = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" ;
/* Retorna o valor absoluto de cada caractere
* no alfabeto. */
long int index_alfabeto(char c) {
char *p ;
if((p=strchr(alfabeto, c))) {
return (long int)(p - alfabeto);
} else {
return (long int)NULL ;
}
}
/* Utiliza o método da expansão para converter
* um número na base N para a base 10.
* Entradas: Uma string numérica na base N.
* Base numérica do 1o parâmetro.
* Saída : Saída inteira do resultado.
*/
long int baseNtobase10(char *strnum, int basen) {
long int outnum = 0;
long int exp = 1;
long int index;
index = strlen(strnum) - 1;
if(index <= 0) return -1 ;
while(index >= 0) {
outnum += index_alfabeto(strnum[index])*exp;
index-- ; exp = exp * basen ;
}
return outnum ;
}
/* Utiliza o método da divisão para converter
* um número na base 10 para a base N.
* Entradas: Buffer para armazenar o resultado.
* Inteiro na base 10.
* Base de saída.
* Saída : String numérica na base M.
*/
void base10tobaseM(char *str, long int inpnum, int basem) {
int istr = 0;
/* Número zero. */
if(inpnum == 0) {
str[0]='0'; istr=1;
}
/* Mapeia o resto da divisão no alfabeto e
* faz do quociente o novo dividendo. */
while(inpnum) {
str[istr++]=alfabeto[inpnum%basem];
inpnum /= basem;
}
str[istr]=0 ;
/* Inverte a string. */
if(istr>0) {
char t ;
long int i=0 ;
istr-- ;
while(i <= istr/2) {
t = str[istr-i] ;
str[istr-i] = str[i];
str[i++] = t;
}
}
}
int main(int argc, char **argv) {
char saida[100] ;
long int numbase10 ;
if(argc != 4) {
printf("[uso] ./dbase <num> <baseN> <baseM>\n") ;
return -1 ;
}
/* Os parâmetros são passados diretamente, deveria
* ter uma checagem de erro antes. */
numbase10 = baseNtobase10(argv[1], atoi(argv[2])) ;
base10tobaseM(saida, numbase10, atoi(argv[3])) ;
/* Saída. */
puts(saida) ;
return 0;
}
Exemplo de execução
$ gcc -o dbase dbase.c # Da base 2 para base 10 $ ./dbase 101101101010 2 10 2922 # Da base 4 para base 2 $ ./dbase 103320222 4 2 10011111000101010 # Da base 5 para base 18 $ ./dbase 4443302111 5 18 52EE31 # Da base 16 para base 32 $ ./dbase BEBA 16 32 1FLQ
Referências
[1] Conversão de base numérica by wikipedia (Acessado em: Julho/2012)
http://pt.wikipedia.org/wiki/Convers%C3%A3o_de_base_num%C3%A9rica
[2] Gerando Permutações-r Com Repetição em C, by Daemonio (Acessado em: Julho/2012)
https://daemoniolabs.wordpress.com/2011/02/11/gerando-permutacoes-r-com-repeticao-em-c/
[3] Codificação base64 em C by Daemonio (Acessado em: Julho/2012)
https://daemoniolabs.wordpress.com/2011/09/09/codificacao-base64-em-c/
[4] Algarismo, by wikipedia (Acessado em: Julho/2012)
http://pt.wikipedia.org/wiki/Algarismo
[5] Numeração Decimal by Escola Kids (Acessado em: Julho/2012)
http://www.escolakids.com/numeracao-decimal-1.htm
[6] Conversion of Number Representations by Lionel E. Deimel (Acessado em: Julho/2012)
http://www.deimel.org/comp_sci/conversion.htm
[7] Mudança de base no Linux by Daemonio (Acessado em: Julho/2012)
https://daemoniolabs.wordpress.com/2011/09/15/mudanca-de-base-no-linux/
Dæmonio Labs 
Bem explicadooo o assunto!
Feliz que tenha gostado, tecnogti.
O layout do blog mudou e por isso as partes em cinza ficaram bagunçadas. Vou trocá-las por imagem quando tiver algum tempo livre. Por enquanto, façam uma cópia delas para algum editor de texto para visualizá-las corretamente.
Abraços
Por que a base 2 é tão importante para o sistema computacional?
os dados são salvos em memória como “ligado” ou “desligado”. Esses dois estados podem ser representados como 1 para “ligado” e 0 para “desligado”, por isso a base dois é tão importante. A escolha da base 2 tem a ver com a física do hardware (sinais elétricos) e pela facilidade da distinção entre dois valores, como ligado (com sinal) e desligado (sem sinal).