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; }