#
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)`

.