11.10 Reversing a Bit String

Another common programming project instructions assign, and a useful function in its own right, is a program that reverses the bits in an operand. That is, it swaps the L.O. bit with the H.O. bit, bit 1 with the next-to-H.O. bit, and so on. The typical solution an instructor probably expects for this assignment is the following:

 // Reverse the 32-bits in EAX, leaving the result in EBX:              mov( 32, cl ); RvsLoop:     shr( 1, eax );     // Move current bit in EAX to the carry flag.              rcl( 1, ebx );     // Shift the bit back into EBX, backwards.              dec( cl );              jnz RvsLoop

As with the previous examples, this code suffers from the fact that it repeats the loop 32 times for a grand total of 129 instructions. By unrolling the loop you can get it down to 64 instructions, but this is still somewhat expensive.

As usual, the best solution to an optimization problem is often a better algorithm rather than attempting to tweak your code by trying to choose faster instructions to speed up some code. However, a little intelligence goes a long way when manipulating bits. In the last section, for example, we were able to speed up counting the bits in a string by substituting a more complex algorithm for the simplistic "shift and count" algorithm. In the example above, we are once again faced with a very simple algorithm with a loop that repeats for one bit in each number. The question is: "Can we discover an algorithm that doesn't execute 129 instructions to reverse the bits in a 32-bit register?" The answer is yes, and the trick is to do as much work as possible in parallel.

Suppose that all we wanted to do was swap the even and odd bits in a 32-bit value. We can easily swap the even an odd bits in EAX using the following code:

         mov( eax, edx );         // Make a copy of the odd bits in the data.         shr( 1, eax );           // Move the even bits to the odd positions.         and( $5555_5555, edx );  // Isolate the odd bits by clearing even bits.         and( $5555_5555, eax );  // Isolate the even bits (in odd posn now).         shl( 1, edx );           // Move the odd bits to the even positions.         or( edx, eax );          // Merge the bits and complete the swap.

Of course, swapping the even and odd bits, while somewhat interesting, does not solve our larger problem of reversing all the bits in the number. But it does take us part of the way there. For example, if after executing the preceding code sequence you swap adjacent pairs of bits, you've managed to swap the bits in all the nibbles in the 32-bit value. Swapping adjacent pairs of bits is done in a manner very similar to the above, the code is

         mov( eax, edx );         // Make a copy of the odd-numbered bit pairs.         shr( 2, eax );           // Move the even bit pairs to the odd posn.         and( $3333_3333, edx );  // Isolate the odd pairs by clearing even pairs.         and( $3333_3333, eax );  // Isolate the even pairs (in odd posn now).         shl( 2, edx );           // Move the odd pairs to the even positions.         or( edx, eax );          // Merge the bits and complete the swap.

After completing the preceding sequence you swap the adjacent nibbles in the 32-bit register. Again, the only difference is the bit mask and the length of the shifts. Here's the code:

         mov( eax, edx );         // Make a copy of the odd-numbered nibbles.         shr( 4, eax );           // Move the even nibbles to the odd position.         and( $0f0f_0f0f, edx );  // Isolate the odd nibbles.         and( $0f0f_0f0f, eax );  // Isolate the even nibbles (in odd posn now).         shl( 4, edx );           // Move the odd pairs to the even positions.         or( edx, eax );          // Merge the bits and complete the swap.

You can probably see the pattern developing and can figure out that in the next two steps you have to swap the bytes and then the words in this object. You can use code like the above, but there is a better way: Use the bswap instruction. The bswap (byte swap) instruction uses the following syntax:

                   bswap( reg₃₂ );

This instruction swaps bytes zero and three, and it swaps bytes one and two in the specified 32-bit register. The principle use of this instruction is to convert data between the so-called little endian and big-endian data formats.^[2] Although you don't specifically need this instruction for this purpose here, the bswap instruction does swap the bytes and words in a 32-bit object exactly the way you want them when reversing bits. Rather than sticking in another 12 instructions to swap the bytes and then the words, you can simply use a "bswap( eax );" instruction to complete the job after the instructions above. The final code sequence is

         mov( eax, edx );         // Make a copy of the odd bits in the data.         shr( 1, eax );           // Move the even bits to the odd positions.         and( $5555_5555, edx );  // Isolate the odd bits by clearing even bits.         and( $5555_5555, eax );  // Isolate the even bits (in odd posn now).         shl( 1, edx );           // Move the odd bits to the even positions.         or( edx, eax );          // Merge the bits and complete the swap.         mov( eax, edx );         // Make a copy of the odd numbered bit pairs.         shr( 2, eax );           // Move the even bit pairs to the odd posn.         and( $3333_3333, edx );  // Isolate the odd pairs by clearing even pairs.         and( $3333_3333, eax );  // Isolate the even pairs (in odd posn now).         shl( 2, edx );           // Move the odd pairs to the even positions.         or( edx, eax );          // Merge the bits and complete the swap.         mov( eax, edx );         // Make a copy of the odd numbered nibbles.         shr( 4, eax );           // Move the even nibbles to the odd position.         and( $0f0f_0f0f, edx );  // Isolate the odd nibbles.         and( $0f0f_0f0f, eax );  // Isolate the even nibbles (in odd posn now).         shl( 4, edx );           // Move the odd pairs to the even positions.         or( edx, eax );          // Merge the bits and complete the swap.         bswap( eax );            // Swap the bytes and words.

This algorithm only requires 19 instructions, and it executes much faster than the bit-shifting loop appearing earlier. Of course, this sequence does consume a bit more memory. If you're trying to save memory rather than clock cycles, the loop is probably a better solution.

^[2]In the little endian system, which is the native 80x86 format, the L.O. byte of an object appears at the lowest address in memory. In the big endian system, which various RISC processors use, the H.O. byte of an object appears at the lowest address in memory. The bswap instruction converts between these two data formats.