April 18th, 2010 by JuanK

El título de este post debería ser realmente: “Cómo formatear una cadena para mostrar un entero en formato binario”… pero créanme que nadie lo buscaría así en un buscador .

Bien esto parece ser un problema recurrente alrededor de los foros en internet, existen muchas soluciones diferentes a este problema, incluso hay algunos lenguajes que ya incluyen soporte para hacer esto fácilmente,  el CLR no se caracteriza por tener una funcionalidad fácil de utilizar sin embargo en este artículo exploraremos varias soluciones (desde luego no todas )posibles hasta llegar a la solución ideal que espero les sea de provecho a todos.

Estas son las opciones que exploraremos, son básicamente 2.

La primera opción no requiere de mucho análisis pero tiene sus inconvenientes digamos menores. La segunda opción es la que más nos importa, aprenderemos a deducir el algoritmo a implementarlo y subsecuentemente lo iremos optimizando hasta lograr una versión digna de un excelente programador:

1. Convertir con BitVector32 (mala solución pero rápida de implementar)
2. Convertir creando un algoritmo eficiente
   • Utilizando string
   • Utilizando StringBuilder
   • Utilizando punteros con codigo inseguro

1.  CONVERTIR CON BITVECTOR32

Esta es la solución más rápida al problema, pero en mi opinión la menos profesional….

BitVector32 es una colección especializada que se encuentra en:

System.Collections.Specialized

Esta clase provee una estructura simple que almacena valores boléanos que representan un entero de 32 bit.  Que que?

Ok esta explicación no necesariamente es clara para todos, hagámoslo muy simple veamos un entero de 32 bits, imaginemos que en memoria se ve así:

Es decir cada casilla representa un bit, para completar así 32 bits.

Bien entonces esto a final de cuentas es una colección bits, es decir en cada ‘celda’ podemos tener dos valores posibles 1 o 0… true o false.

Bien eso es lo hace BitVector toma un entero y lo permite manejar como un array de booleanos.

El método ToString() permite convertir todo esto a 1s y 0s para poder ver los valores de cada ‘celda’ en su representación numérica, sin embargo esto tiene un inconveniente pues si utilizamos elObjetoBitVector.ToString() recibiremos algo así como esto:

BitVector32{00000000000000000000000001101111}

Nos sobra algo al principio y al final… a nosotros solo nos interesan los datos binarios así que la solución es hacer un substring de la parte de la cadena que nos interesa, finalmente el código quedaría así:

public static string EB_BitVector32(Int32 entero)
{
    BitVector32 bv = new BitVector32(entero);
    return bv.ToString().Substring(12, 32);
}

Esto nos produciría este resultado similar a:

00000000000000000000000001101111

2.  CONVERTIR CREANDO UN ALGORITMO EFICIENTE

Ahora si entremos en materia hagamos el algoritmo.

Una de las primeras ideas que a uno se le viene a la mente es utilizar el conocido algoritmo que nos permite convertir un numero decimal a base 2, para el que no lo recuerde o no lo conozca: es un algoritmo que toma como base divisiones anidadas del valor entre 2 y recupera los residuos. En este link tienen una explicación detallada al respecto: Decimal a Binario

Sin embargo dicho algoritmo puede ser ineficiente para nuestro gusto.

Retomemos conceptos como puntos clave que nos permitan llegar a un algoritmo óptimo:

1. Básicamente un entero es un arreglo de 4 bytes (32 bits)
   
2. Por cada bit se debe producir su equivalente como cadena (“0″ , “1″) según si el bit esta prendido(1) o apagado(0)
   
3. Podemos acceder a todos los bit como un arreglo de boolean a través de BitVector32, pero en ese caso la solución sería aún más lenta que utilizando la propuesta inicial que usa BitVector32
   
4. Hay que encontrar el mecanismo adecuado para recorrer los bit

De los conceptos clave tenemos que los dos primeros nos son útiles, el tercero no nos aporta nada nuevo y el cuarto es nuestra necesidad más inmediata: Averiguar como recorrer los bit sin necesidad de usar BitVector32.

Lo primero que me salta a la mente es usar operadores binarios especialmente corrimientos de bit (<<) y and (&) para las máscaras.

Veamos un poco de teoría acerca de lo que haremos.

1. Crear un bucle e 32 ciclos
   
2. Leemos siempre el valor del primer bit del entero de 32 bit, esto lo podemos hacer efectuando un and binario (&) del entero con un numero que tenga el primer bit prendido únicamente, es decir con : 0×80000000 (es decir 2147483648 )… porqué este número?  bueno coloquemos este 0×80000000 en nuestro arreglo de 32 bits:
   

   1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
   8				0				0				0				0				0				0				0

   Cada 4 bits representan uno de los dígitos hexa, de esta forma el 0×8 esta representado por los primeros 4 bits, en efecto 1000 = 0×8, así que si se fijan en nuestro arreglo de bits solo tenemos un bit prendido, de tal forma que cualquier cosa que haga & con 0×80000000 solo podría llegar a tener prendido el bit 1, así podemos hallar que valor tiene el bit 1 de un número dado ya que si ese bit esta en 0 al hacer and quedaría en 0, mientras que si esta en 1 al hacer and quedaría en uno nuevamente. Concretando, cuando hacemos un and entre dos enteros y uno de los enteros es 0×80000000 el resultado siempre será el valor del primer bit del otro entero. ( espero haber sido claro).

3. En cada iteración corremos 1 bit posición a la izquierda (<< 1), de tal forma que el primer bit es reemplazado por el bit siguiente
   
4. Se regresa al paso 2

IMPLEMENTACION CRUDA Utilizando String

Este es el código resultante de la implementación más simpe del algoritmo:

public static string EB_String(int entero)
{
    //La máscara y el # de iteraciones
    const uint mascara = 0x80000000;
    const int iteraciones = 32;
    //el contador y el resultado
    int contador = 0;
    string resultado = "";

    //Se recorren los 32 bit
    while (contador++ < iteraciones)
    {
        /*Si el entero and la mascara = 0 quiere decir
         *que el bit 1 esta apagado*/
        if ((entero & mascara) == 0)
            resultado += "0";
        else
            resultado += "1";

        /*correr un bit a la izquierda para poner
         *el siguiente bit en la posicion del primero*/
        entero = entero << 1;
    }
    return resultado;
}

OPTIMIZACIÓN DE CÓDIGO Utilizando StringBuilder

La implementación anterior es susceptible de una sencilla mejora utilizando StringBuilder ya que al ser string un tipo inmutable , las recurrentes concatenaciones generadas al utilizar masivamente el método sobrecargarían el GC, sin contar el overhead producido por las frecuentes reservas de memoria (1 adicional por cada cambio al string). StringBuilder se encuentra en el namespace System.Text.

Código optimizado utilizando StringBuilder:

public static string EB_StringBuilder(int entero)
{
    //La máscara y el # de iteraciones
    const uint mascara = 0x80000000;
    const int iteraciones = 32;
    //el contador y el resultado
    int contador = 0;
    StringBuilder resultado = new StringBuilder(iteraciones);

    //Se recorren los 32 bit
    while (contador++ < iteraciones)
    {
        /*Si el entero and la mascara = 0 quiere decir
         *que el bit 1 esta apagado*/
        if ((entero & mascara) == 0)
            resultado.Append('0');
        else
            resultado.Append('1');

        /*correr un bit a la izquierda para poner
         *el siguiente bit en la posicion del primero*/
        entero = entero << 1;
    }
    return resultado.ToString();
}

OPTIMIZACIÓN DE CÓDIGO Utilizando punteros – código unsafe

Aunque StringBuilder ya proporciona una mejora muy importante, dadas las características de nuestro problema(concatenación uno a uno) resulta mucho más idóneo generar código que utilice punteros. Es importante tener en cuenta que para que este código funcione se requiere modificar las propiedades del proyecto para que admita código unsafe.

Esta es la versión básica con manejo de apuntadores:

public static unsafe string EB_Unsafe(int entero)
{
    const uint mascara = 0x80000000;
    const int iteraciones = 32;

    int contador = 0;

    //Se reservan 32 posiciones y uno adicional para
    //terminacion en null
    char* resultado = stackalloc char[iteraciones + 1];
    //puntero de trabajo
    char* aux = resultado;

    while (contador++ < iteraciones)
    {
        if ((entero & mascara) == 0)
            *aux = '0';
        else
            *aux = '1';

        //Mover el puntero una posicion dentro de la cadena
        aux++;

        entero = entero << 1;
    }
    return new string(resultado);
}

Esta es la versión final de “bonus” totalmente optimizada para velocidad de procesamiento, es levemente diferente de la anterior para realizar la menor cantidad de validaciones posibles y para que ignore los 0s a la izquierda, lo cual la hace excepcionalmente rápida en la mayoría de los casos. Revísenla…:

public static unsafe string EB_Unsafe_Opt(int entero)
{
    const uint mascara = 0x1;
    const int iteraciones = 32;

    char* resultado = stackalloc char[iteraciones + 1];
    char* aux = resultado + iteraciones - 1;

    do
    {
        if ((entero & mascara) == 0)
            *(aux--) = '0';
        else
            *(aux--) = '1';

        entero = entero >> 1;
    } while (entero != 0);

    return new string(++aux);
}

Si alguien tiene una solución mejor por favor no dude en compartirla!!

En unos días publicare un programa especialmente diseñado para medir la velocidad de cada una de estas alternativas… les adelanto que las diferencias de tiempo van casi hasta de 20 o 30 veces más velocidad.

Happy Learning!!!

OOOHH OLvidaba decirles Si quieren pueden usar:

System.Convert.ToString(elValor, 2);

jajajajaja, bueno el ejercicio que hicimos produce un resultado 30% más rápido.