miguel jimenez en español // MVP C#

Hace un par de dias mi amigo Ricardo Varela comenzo a bloggear en español (en paralelo con su actual blog en inglés). Miembro activo de comunidades Microsoft, trabaja actualmente en Google UK. Pero lo relevante es que en su nuevo blog ha comenzado con un post con algo de acertijos de programación, volviendo a lo básico, a los principios del desarrollo. Esto va a ser divertido.

Bein, esta es mi respuesta a su post. Habia tres preguntas relacionadas con estructuras de datos y modos de pensar alternativos sobre como dar la vuelta a las cosas.

• Sabes dar la vuelta a una cadena de texto? Por ejemplo, si tienes "abc" la cadena de retorno debería ser "cba"

Esto parecía bastante sencillo. En C# cadena se representa como un array de caracteres, por tanto puedes usar el indexador para obtener el caracter de una posición y darles la vuelta "manualmente" con algo como:

string inputString = "abc";
string reversedString = string.Empty;

for (int c = inputString.Length; c > 0; c--)
{
    reversedString += inputString[c - 1];
}

Console.WriteLine("Original String: " + inputString);
Console.WriteLine("Reversed String: " + reversedString);

O puedes usar la funcionalidad del framework de .NET para hacerlo de manera mas "elegante":

char[] chars = inputString.ToCharArray();
Array.Reverse(chars);

// Use the reversed array of chars

• Un poco más profundo en estructuras de datos,  sabrías dar la vuela a los bits de un byte? Por ejemplo, si tenemos 1 el byte de retorno debería ser 128

Debo admitir que esta ha sido dificil. Aunque tengo perfectamente claro los conceptos de bits, bytes y operaciones bitwise, el lenguaje C# no ofrece una manera sencilla y estructurada de acceder a esos elementos fundamentales de las estructuras de datos. Finalmente consegui hacerlo. La estructura de datos más pequeña disponible para representar el interior de un byte que he encontrado es un simple byte, así que solo queda rellenarlo coon los valroes para cada byte:

static byte[] getBits(byte inputByte)
{
    byte[] bits = new byte[8];

    for (int p = 0; p < 8; p++)
    {
        bits[7 - p] = (byte)(1 & (inputByte >> p));
    }

    return bits;
}

Sencillo? Vale, lo explico un poco... el operador bitwise >> simplemente desplaza los bits del byte hacia la derecha, así que si desplazamos 01010101 una posición a la derecha obtenemos 00101010... después una simple operacion AND logica con la máscara 00000001 para determinar si el bit esta marcado. Almaceno el estado de cada bit en el array de salida y lo devuelvo. Como nota rápida, el array de bits se puede obtener dado la vuelta directamente si cambio la linea dentro del bucle for a:

bits[p] = (byte)(1 & (inputByte >> p));

Pero unos métodos genericos para convertir entre byte y bits suena un poco mejor, así que no lo he incluido directamente en ese método. Una vez que tenemos el array, es sencillo darle la vuelta con los métodos mostrados anteriormente para las cadenas:

Array.Reverse(bits);

Y ahora, solo tenemos que ser capaces de convertir el array de bits de vuela a un byte:

static byte setBits(byte[] bits)
{
    byte obyte = bits[0];

    for (int p = 1; p < 8; p++)
    {
        obyte = (byte)((obyte << 1) + bits[p]);
    }

    return obyte;
}

El método es similar al usado para extraer los bits, pero esta vez el operador bitwise << desplaza los bits a la izquierda, de forma que puedo incrementar el número hasta que alcanza el valor marcado. Un sencillo programa para probar como funciona podria ser:

byte inputByte = 1;
byte outputByte = 0;

byte[] bits = getBits(inputByte);
Array.Reverse(bits);
outputByte = setBits(bits);

Console.WriteLine("Input Byte: " + inputByte);
Console.WriteLine("Reversed Byte: " + outputByte);

• Y la más compleja. Los números de coma flotante se representan habitualmente con el estándar IEEE 754, serías capaz de dar la vuela a los bits de un numero en coma flotante? Por ejemplo, si tenemos 118.625f la salida debería ser -17180580000f

Wow! Esta era realmente complicada. No conocia el funcionamiento del estandar IEEE 754 así que me lo he leído en la wikipedia (la página de este estandar en el IEEE está en revisión y no había información disponible) y parece que es relativamente sencillo. La representación en coma flotate es una estructura de datos de 32bits con la siguiente información: 

Ahora me parece algo más sencillo. Simplemente hemos de dar la vuelta a los bits, en C# los dos tipos de coma flotante son float y double, el primero para almacenar con precisión de 32bits y el segundo con 64bits; el problema es que estos tipos no permiten operaciones bitwise, y necesito crear algun método nuevo basado en la clase BitConverter.

Es probable que esto se pueda refactorizar para que solo un par de métodos resuelvan todas las necesidades de operaciones con bits, pero el objetivo era dar la vuelta a un numero en coma flotante, así que alla vamos:

static byte[] getFloatingBits(double input)
{
    byte[] bytes = BitConverter.GetBytes(input);

    if (BitConverter.IsLittleEndian)
    {
        Array.Reverse(bytes);
    }

    byte[] bits = new byte[64];

    for (int i = 0; i < 8; i++)
    {
        Array.Copy(getBits(bytes), 0, bits, i * 8, 8);
    }

    return bits;
}

Explico el método un poco... El tipo float se puede dividir en 4 bytes y el método BitConverter.GetBytes nos da un array de esos bytes, pero desafortunadamente no incluye un método que nos permita reconvertir dicho array en un float, así que uso el tipo double y casting :(

La lógica es muy sencilla, extraemos los 8 bytes de la doble precisión de coma flotante. Despues, verificamos si el procesador es LittleEndian y en ese caso damos la vuelta a los bytes para reflejar el verdadero valor. Copiamos todo a un array de bits, y ya estamos. Ahora solo nos queda dar la vuelta al array de bits:

Array.Reverse(bits);

Y volver al método que nos permite invertir el proceso para obtener un número de coma flotante a partir de un array de bits:

static double setFloatingBits(byte[] bits)
{
    byte[] bytes = new byte[8];

    for (int i = 0; i < 8; i++)
    {
        byte[] actualByte = new byte[8];
        Array.Copy(bits, i * 8, actualByte, 0, 8);
        
        bytes = setBits(actualByte);
    }

    if (BitConverter.IsLittleEndian)
    {
        Array.Reverse(bytes);
    }

    return BitConverter.ToDouble(bytes, 0);
}

El problema es que el número esperado no coincide con el resultado obtenido con este método para dar la vuelta al array de bits completo. De hecho, he releido la pregunta y dice "eres capaz de dar la vuelta al orden de bits de exponente y mantisa?" ... He hecho exactamente eso también, cambiar los bits solo de mantisa y exponente, obteniendo los siguientes arrays de bits:

Original: 0 10000000 10111011010100000000000
Reversed: 0 00000001 00000000000101011011101
Expected: 1 10000100 00100000000000000101011

Pero el numero que hemos dado la vuelta no representa el que Ricardo indicaba en su post. Que estoy haciendo mal? Hay algo mal en mi modo de afrontar el problema o el número experado es inncorrecto? Tengo bastante curiosidad sobre porque hay un bit menos (como 1) en el numero esperado y como se ha cambiado el signo.