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

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:

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 // mask11110000 // 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 blocks0000111111110000 // mask shifted left by block-size/20000111100001111 // 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!