Before you go, check out these stories!

0
Hackernoon logoReversing an n-bit number in O(log n) time by@ehudt

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

Author profile picture

@ehudtEhud Tamir

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 // 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 blocks
0000111111110000 // mask shifted left by block-size/2
0000111100001111 // 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!

Tags

Join Hacker Noon

Create your free account to unlock your custom reading experience.