### Question

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as **00000010100101000001111010011100**), return 964176192 (represented in binary as **00111001011110000010100101000000**).

**Follow up**:

If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

**Credits:**

Special thanks to @ts for adding this problem and creating all test cases.

### Analysis

This question is standard bit manipulation. We essentially get bits one by one from n, and append it to the result.

However, the question ask how to optimize it, to improve its performance. Em, that’s interesting.

### Solution

First code is the standard solution.

I found another interesting solution from programcreek, which uses “swap bits” method. I’ve never seen this before, so I posted his solution below.

But is it really a faster solution?

Finally, I found something in 书影 博客, quoted as below:

以4位为单位执行反转，将0x0至0xF的反转结果预存在一个长度为16的数组中，反转时直接查询即可。

Thus this is the best solution for performance.

### Code

My code

```
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
int last = n & 1;
n >>= 1;
result <<= 1;
result = result | last;
}
return result;
}
}
```

“swap bits”

```
public int reverseBits(int n) {
for (int i = 0; i < 16; i++) {
n = swapBits(n, i, 32 - i - 1);
}
return n;
}
public int swapBits(int n, int i, int j) {
int a = (n >> i) & 1;
int b = (n >> j) & 1;
if ((a ^ b) != 0) {
return n ^= (1 << i) | (1 << j);
}
return n;
}
```

Best solution:

```
char tb[16] = {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};
uint32_t reverseBits(uint32_t n) {
int curr = 0;
uint32_t ret = 0;
uint32_t msk = 0xF;
for(int i = 0; i < 8; i++) {
ret = ret << 4;
curr = msk&n;
ret |= tb[curr];
n = n >> 4;
}
return ret;
}
```