viernes, 29 de julio de 2011

Cambiando de base

Hace poco me he visto en la necesidad de tener que cambiar de base algunos números, desde la típica base 10 a cualquier otra elegida arbitrariamente. No limitandome a sólo esto, también introduje la posibilidad de cambiar el alfabeto, de forma que se obtienen interesantes resultados.

De esta forma, el alfabeto (conjunto de símbolos) que habitualmente usamos para contar es 0123456789, el alfabeto que usamos en binario es 01 y el alfabeto que por lo general usamos para hexadecimal es 0123456789ABCDEF. Sin embargo podríamos definir cualquier otro, representando igualmente los mismos números.

El algoritmo para cambiar de base un número consiste en ir obteniendo los restos de ir dividiendo el número original por la base. El primer resto representa la cifra menos significativa del número en la nueva base, el segundo la segunda cifra, y así hasta que el cociente resulte menor que la base no pudiéndose realizar más divisiones. Cuando el algoritmo termina se añade el último cociente como cifra más significativa al resultado. Para cada una de las nuevas cifras se busca cada resultado en la cadena del alfabeto, para saber qué símbolo lo representará.

Implementando todo lo descrito en C++ el algoritmo quedaría así:

string rebase(const unsigned int number,
     const string& alphabet)
{
 const unsigned int base = alphabet.length();
 string rebased = "";
 unsigned int rem = 0;
 unsigned int n = number;
 while (n >= base)
 {
  rem = n % base;
  n = n / base;
  rebased = string(1,alphabet[rem]) + rebased;
 }
 rebased = string(1,alphabet[n]) + rebased;
 return rebased;
}

Vamos a ver qué resultados se obtienen probando con distintas bases:

Numero: 24
Alfabeto: 01
Conversion: 11000

Numero: 24
Alfabeto: 01234567
Conversion: 30

Numero: 24
Alfabeto: 0123456789
Conversion: 24

Numero: 24
Alfabeto: 0123456789ABCDEF
Conversion: 18

Como se puede observar hemos transformado el número 24 a sus distintas representaciones en base 2 (binario), 8 (octal) y 16 (hexadecimal).

Veamos ahora qué sucede si, por ejemplo, queremos aprovechar este algoritmo para realizar un numerado usando sólo letras, tal y como puedan hacer algunos tipos de listas de procesadores de texto o las columnas de una hoja de cálculo. De esta forma habría que empezar por A, luego B, C y así hasta Z. Tras Z llegaría AA, AB, AC, ..., AZ, BA, BB, BC, ..., ZZ, AAA, AAB, AAC, etc.

Tentativamente podemos tomar como alfabeto ABCDEFGHIJKLMNOPQRSTUVWXYZ y ver los resultados iniciales:

Numero: 0
Alfabeto: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Conversion: A

Numero: 1
Alfabeto: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Conversion: B

Numero: 25
Alfabeto: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Conversion: Z

Hasta ahí tiene buena pinta. Veamos ahora qué sucede con números un poco más grandes:

Numero: 26
Alfabeto: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Conversion: BA

Numero: 27
Alfabeto: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Conversion: BB

Al pasar a dos cifras no ha aparecido una A como primer caracter tal y como nos gustaría, sino una B. Analicemos el problema para hallar una solución.

Cuando contamos en base 10, 2, 16 o la que sea tenemos el cero, elemento neutro en la suma, por el cual se empieza. Tras agotar los símbolos del alfabeto se incrementa la cifra a la izquierda y se vuelve a empezar a la derecha. Por ejemplo: tras el 9 incrementamos la cifra a su izquierda (que es cero pero no se representa) y sustituimos el 9 por el primer símbolo de nuevo, cero. Así, tras el 9 viene el 10. Al llegar al 19 incrementamos el 1 y sustituimos de nuevo el 9 por 0, teniendo 20.

Aplicando esto a nuestro caso particular de letras, la A representaría el 0, y la B el 1. De esta forma al llegar a la Z incrementamos el caracter a su izquierda (la A-cero, que no estaba representada) y sustituimos la Z por el primer símbolo del alfabeto, la A, quedando BA.

Visto el origen del problema vamos a hallar una solución.

string alphaOrder(const unsigned int number)
{
 const string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 const unsigned int base = alphabet.length();
 string rebased = "";
 unsigned int rem = 0;
 unsigned int n = number;
 while (n >= base)
 {
  rem = n % base;
  n = n / base - 1;
  rebased = string(1,alphabet[rem]) + rebased;
 }
 rebased = string(1,alphabet[n]) + rebased;
 return rebased;
}

En la línea 11 añadimos un -1. De esta forma se ajusta en cada iteración el cociente para que la A aparezca como primer caracter con valor (haciendo las veces de 1) y se solucione nuestro problema.

Con este cambio aplicado veamos cómo se comporta el código, ya de forma correcta.

Numero: 0
Conversion: A

Numero: 1
Conversion: B

Numero: 25
Conversion: Z

Numero: 26
Conversion: AA

Numero: 27
Conversion: AB

Numero: 100
Conversion: CW

Numero: 1000
Conversion: ALM

Como era de esperar se obtienen los resultados que deseamos. Ya para terminar listo a continuación la totalidad del código que he empleado para estos ejemplos, de forma que cada uno pueda experimentar con él como le plazca :D

// rebase.cpp - Created on 2010.10.24

#include <iostream>
#include <string>

using namespace std;

string rebase(const unsigned int number,
     const string& alphabet)
{
 const unsigned int base = alphabet.length();
 string rebased = "";
 unsigned int rem = 0;
 unsigned int n = number;
 while (n >= base)
 {
  rem = n % base;
  n = n / base;
  rebased = string(1,alphabet[rem]) + rebased;
 }
 rebased = string(1,alphabet[n]) + rebased;
 return rebased;
}

string alphaOrder(const unsigned int number)
{
 const string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 const unsigned int base = alphabet.length();
 string rebased = "";
 unsigned int rem = 0;
 unsigned int n = number;
 while (n >= base)
 {
  rem = n % base;
  n = n / base - 1;
  rebased = string(1,alphabet[rem]) + rebased;
 }
 rebased = string(1,alphabet[n]) + rebased;
 return rebased;
}

void testRebase(const unsigned int number,
     const string& alphabet)
{
 cout << "Numero: " << number << endl;
 cout << "Alfabeto: " << alphabet << endl;
 cout << "Conversion: " << rebase(number,alphabet) << endl << endl;
}

void testAlpha(const unsigned int number)
{
 cout << "Numero: " << number << endl;
 cout << "Conversion: " << alphaOrder(number) << endl << endl;
}

int main()
{
 testRebase(24, "01");
 testRebase(24, "01234567");
 testRebase(24, "0123456789");
 testRebase(24, "0123456789ABCDEF");
 testRebase( 0, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
 testRebase( 1, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
 testRebase(25, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
 testRebase(26, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
 testRebase(27, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
 testAlpha(0);
 testAlpha(1);
 testAlpha(25);
 testAlpha(26);
 testAlpha(27);
 testAlpha(100);
 testAlpha(1000);
 return 0;
}


No hay comentarios: