**What Working at Amazon Taught Me About Growth and Engineering**

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 // 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

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!

L O A D I N G

. . . comments & more!

. . . comments & more!