# 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 Leetcode.com 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)`.