# [LeetCode 190] Reverse Bits

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

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:

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;
}
``````