Conversão de base numérica

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

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

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/

5 pensamentos sobre “Conversão de base numérica

  1. 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

    • 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).

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s