Last week, while writing my , I came across an interesting algorithm for reversing an integer. For example, it takes and transform it into . What’s cool about this algorithm, is that it does it in O(log n) iterations. This is the code: previous post 10100011 11000101 Creating the mask Another cool trick lies in how is created. is composed of alternating blocks of 0s and 1s of size each. The mask starts as an all-1s number, and updated on the first line of the loop: mask mask s while ((s >>= 1) > 0) {mask ^= (mask << s);... This happens right after is halved, so is then half of 's block size. On the first iteration, , and . The mask is updated by XORing itself with another copy of itself left-shifted by places: s s mask mask == 11111111 s == 4 s mask =11111111 XOR // mask11110000 // mask << s= 00001111 XOR of two bits is 1 if-and-only-if they are 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: not equal 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 below! leave a response
