## Before you go, check out these stories!

0 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:

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 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!                Join Hacker Noon