[LeetCode 190] Reverse Bits

Question

link

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.

            <div id="tags" class="btn btn-xs btn-warning">Show Tags</div>
            <span class="hide">
              
              <a class="btn btn-xs btn-primary" href="/tag/bit-manipulation/">Bit Manipulation</a>
              
            </span>
          
        </div>

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