Reverse Bits

9 Dec 2011

Given an integer of n bits, reverse the bits.

I am not very creative in solving a problem. Of course, everyone, including me, can come up with O(n) solution.

The real rock-star will come up with O(log n) solution… Yes, it is possible.

I have to remember this. Reversing anything can be solved with the divide-and-conquer technique.

Divide and Conquer reversing

Let's say we have:

a b c d e f g h

We can divide into:

[a b c d] [e f g h] [[a b] [c d]] [[e f] [g h]]

Then we swap and combine:

[[b a] [d c]] [[f e] [h g]] [[d c] [b a]] [[h g] [f e]] [d c b a] [h g f e] [h g f e] [d c b a] h g f e d c b a

Walla! That's pretty amazing. The reversing problem can be solved with divide-and-conquer technique.

Now if I can come up with an O(1) technique that swaps all pairs at the same time, the solution will be complete. So, how to swap them?

The solution on uses shift operation as if it is O(1).

After googling for a while, shift operation is implemented by hardware and is indeed O(1).

Give it a kudos