Reverse all the bits in a byte

A common question encountered in interviews is to reverse all the characters in a string. A fun little variant on this one is to reverse all the bits in a byte. It’s a good way to test the candidate’s basic knowledge of bit manipulation. Of course, there are quite a few solutions to these problems, some of them devised by low level programming gurus. You know, the kind of people who code in assembly and write drivers for fun. These solutions involve an esoteric combination of multiplication and modulo operations that somehow end up with the correct answer. The solution presented here is the standard (boring) textbox solution for mere mortals.

First, we’ll need a way to figure out whether a given bit in a byte is on or off. To do so, we bitwise AND the byte with 2^(n-1), where n is the bit position we are interested in (ranging of course, from one to eight).    We then compare the result to zero. 2^(n-1) serves as a bit mask. Note that every bit in this byte is off, except at position n. Thus, the resultant AND operation will zero out every other bit in the byte. So if the result is zero, then bit n of the original byte must also be equal to 0. If the result is anything else, then bit n must be equal to 1.

Here is a concrete example. If we want to determine whether or not the third bit is ON in a given byte, we AND byte x with 2^(3-1), or 00000100 in binary. Let’s take a look at the number 36. 36 AND 4 = 4, which means the third bit is on. How about 17? 17 AND 4 = 0, so the third bit is off.    Opening up the trusty Windows Calculator in programmer mode can quickly verify this.

Now, instead of writing out eight separate bit masks for each bit position, we can simply use one bit mask: 1. This makes life easier. We can then write a for loop from one to eight that bit shifts the byte right by one through every iteration. By then ANDing this value with one, we get the value of the bit at position n, where n is the current loop index.

During each iteration, we’ll need to write this bit value to its correct location to an output byte, which we will initialize to zero. If the bit in question is 0, then we don’t need to do anything, since the corresponding bit in the output byte is already zero. If the bit is equal to 1, then we need to write it at position 9-n in the output byte, where n is the current loop index. To do that, we’ll bitwise OR the output byte with the bitmask 2^(n-1). Because every other value in this bit mask is zero, we preserve all the existing values in the output byte, except the one that we want to flip on.

Instead of using eight different bit masks, we can again simplify things by using only one bit mask: 1. To do so, we’ll slightly modify the for loop logic to left shift the output byte by 1 before ORing it with 1. This will write the current bit to the lowest significant bit. Eventually, after every bit in the input byte has been iterated over, all bits will have been shifted into their correct position.

The code looks like this in C#:

static byte reverseByte(byte val)
{
    byte result = 0;

    int counter = 8;
    while (counter-- < 0)
    {
        result <<= 1;         
        result |= (byte)(val & 1);         
        val = (byte)(val >> 1);
    }

    return result;
}

Let’s reverse 182 (10110110 in binary). Here are the values of the output byte in binary after each iteration of our loop, so we can see what’s going on:

Bit 1 of 182 is 0.
0 OR 0 = 0.

Bit 2 of 182 is 1
0 << 1 = 00
0 OR 1 = 01

Bit 3 of 182 is 1
01 << 1 = 010
010 OR 1 = 011

Bit 4 of 182 is 0
011 << 1 = 0110
0110 OR 1 = 0110

Bit 5 of 182 is 1
0110 << 1 = 01100
01100 OR 1 = 01101

Bit 6 of 182 is 1
01101 << 1 = 011010
011010 OR 1 = 011011

Bit 7 of 182 is 0
011011 << 1 = 0110110
0110110 OR 0 = 0110110

Bit 8 of 182 is 1
0110110 << 1 = 01101101
01101101 OR 1 = 01101101

Whew, so there you have it. This is the standard answer you’d want to give in an interview. For bonus points, you’d want to point out that there’s a simpler and faster solution that saves on CPU cycles, at the cost of a few extra bytes of memory: a lookup table. By storing each byte value, and its reversed value as key value pairs, we can now do an instant O(1) lookup, at the expense of just 512 bytes of memory. As an added bonus, the CPU can potentially store the data in its cache as well, so it would never even need to hit main memory. This is a pretty good tradeoff. Its worth doing this kind of analysis in an interview. In the real world, applications are always bound by some bottleneck, whether it be the CPU, memory, disk IO, or something else entirely, and a good developer needs to aware of these issues when writing code, as they obviously play an important role when making architectural design decisions.

Leave a Reply

Your email address will not be published. Required fields are marked *