Programming job interview challenge

The folks at Dev 102 posted a programming job interview challenge. It is rather easy, but I figured that it may be a nice change of pace, since my last posting was fairly involved.

The challenge is to reverse the bits in each byte, given a large array of bytes. What is the fastest possible solution?

There are only 256 possible values for an 8-bit integer, so it makes sense to pre-compute the reverse of each ahead of time. Then, we can simply scan through the input, and reverse each byte by a simple array lookup. We pay a small initialization cost, but after that, we can reverse bytes nearly as fast as we can read them.

And how to efficiently reverse a byte? There is an obvious solution which uses a for loop and some bit manipulation. My solution below uses a slightly faster approach. It is a nice trick, and not very difficult, so I will leave the details as an exercise to the reader.

Here is a simple solution in C#:

// Reverses bits in each byte in the array
static void Reverse(byte[] bytes)
{
    // Precompute the value of each reversed byte
    byte[] reversed = new byte[256];
    for (int i = 0; i < 256; i++) reversed[i] = Reverse((byte)i);  

    // Reverse each byte in the input
    for (int i = 0; i < bytes.Length; i++) bytes[i] = reversed[bytes[i]];
}  

// Reverses bits in a byte
static byte Reverse(byte b)
{
    int rev = (b >> 4) | ((b & 0xf) << 4);
    rev = ((rev & 0xcc) >> 2) | ((rev & 0x33) << 2);
    rev = ((rev & 0xaa) >> 1) | ((rev & 0x55) << 1);  

    return (byte)rev;
}

If we are going to be reversing multiple arrays, we can hoist the pre-computation into an initialization routine. And, if handling short arrays is important, we can skip the pre-computation step if the array length is less than 256, and just reverse each byte by calling Reverse(byte).

Not sure what else to add… problem solved!

Tags: Algorithms