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

# 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!                    #### Related Stories

L O A D I N G
. . . comments & more!