Reversing an n-bit number in O(log n)

Last week, while writing my previous post, I came across an interesting algorithm for reversing an integer. For example, it takes 10100011 and transform it into 11000101. What’s cool about this algorithm, is that it does it in O(log n) iterations. This is the code:

Reverse an n-bit number in O(log n). From http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

Yes. 9 lines including signature and closing braces. Let’s see how it works.

The next part studies the code line-by-line. If you are bored by the technicalities, feel free to jump to the animation at the end.

Update: The O(log n) running time complexity applies only to n ≤ machine-word size, which is typically 64-bits today. Thanks to all the people who brought this to my attention.

The technique: Recursive block-swapping

The algorithm works by recursively swapping adjacent blocks of bits, decreasing the block size on every iteration. It starts by swapping 2 blocks of n/2 bits, then 4 blocks of n/4 bits, 8 blocks of n/8 bits, and so on, finishing with n blocks of 1 bit. On every iteration, all pairs of adjacent blocks are swapped in parallel. The result is the reversed number. To swap the blocks in parallel the algorithm uses bit-wise operations and bit-masks.

NOTE: The original code uses a 32-bit input. We’ll use 8-bit integers to make things easier to understand.

Swapping adjacent blocks of bits

Swapping blocks in parallel is done with a specially-crafted bit-mask.

For a block size s, the bit-mask mask is composed of alternating blocks of s zeros and s ones. For example, for s = 4, mask == 00001111. For s = 2, mask == 00110011.

This line uses the mask to swap all pairs of blocks in parallel:

num = ((num >> s) & mask) | ((num << s) & ~mask);

• (num >> s) & mask) moves the even blocks s positions to the right and clears out the odd blocks using the mask.
• (num << s) & ~mask moves the odd blocks s positions to the left and clears out the even blocks using the bit-wise NOT of the mask.
• Bit-wise OR is used to add these results together into the swapped number.

Amazingly simple, isn’t it?

A flower XORed against itself. Original By Sam Oth (User:World Trekker) — Own work, CC BY-SA 2.5, https://commons.wikimedia.org/w/index.php?curid=863943

Creating the mask

Another cool trick lies in how mask is created. mask is composed of alternating blocks of 0s and 1s of size s each. The mask starts as an all-1s number, and updated on the first line of the loop:

while ((s >>= 1) > 0) {
  mask ^= (mask << s);
  ...

This happens right after s is halved, so s is then half of mask's block size. On the first iteration, mask == 11111111, and s == 4. The mask is updated by XORing itself with another copy of itself left-shifted by s places:

mask = 
    11111111 XOR  // mask
    11110000      // mask << s
  = 00001111

XOR of two bits is 1 if-and-only-if they are not equal to each other. In each iteration of the mask update, all blocks are shifted left by half their size. When a block is XORed with the previous mask, half of the block overlaps with zeros and the other half overlaps with ones. This creates 2 blocks in the new mask, each half the size of the previous blocks. Here is an illustration:

0000000011111111  // original mask, 8-bit blocks
0000111111110000  // mask shifted left by block-size/2
0000111100001111  // XORed: new mask, 4-bit blocks

Tying it all together

Here’s a short animation that shows the algorithm in action:

It’s amazing how much depth can be found in 9 lines of code. If you have in mind an interesting piece of code that you’d like me to explore, please leave a response below!