Leetcode : reverse bit

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?

 这个题目肯定是用bit operation来做是最简单的，但是当时没有想到如何去做，就用了下面的方法，用了c++的一些库函数，后来还是去看了下别人是如何用bit operation来解的， 网上的方法很多， 有一位一位转的，有4位一转的，也有做出一个size为256的reverse 表格，每次翻转两个字符直接去查表就可以知道翻转后的值是多少，这样做事最后follow up里面优化的一个方法。


class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        //sanity check
        if (n == 0) return 0;
        unsigned int rst = 0;
        unsigned int tmp = n;
        string s1 = "";
        for (int i = 0; i < 32; i++) {
            if (tmp) {
                char c = tmp%2 + '0';
                s1 = c + s1;
                tmp = tmp/2;
            } else {
                s1 = '0' + s1;
            }
        }
        reverse(s1.begin(), s1.end());
        rst = stoul(s1, NULL, 2);
        return rst;
    }
};

// 下面的代码是利用很常见的reverse的方法，即swap 头尾两个元素，但是在这里是需要进行位操作来进行swap，需要先把高低位的bit取出来，然后进行swap, bit swap是先利用另一个mask，将需要swap的两位置1，其他位为0， 然后跟原数进行^, 结果就是swap了两个bit的结果了。 
下面的做法是o(n)的时间复杂度。
class Solution {
private:
    void swapbit(uint32_t &n, int i, int j) {
        int lo = ((n >> i) & 1);
        int ho = ((n >> j) & 1);
        //if lo != ho
        if (lo ^ ho) {
            n ^= (1 <<i) | (1 <<j);
        }
        return;
    }
public:
    uint32_t reverseBits(uint32_t n) {
        uint k = sizeof(n)*8;//the number of bits in n
        for (int i = 0; i < k/2; i++) {
            swapbit(n, i, k-i-1);
        }
        return n;
    }
};


以下是leetcode上面更加优化的解法，时间复杂度o（1），

2 3 4 5 6 7 8 9

uint reverseMask(uint x) {   assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits).   x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);   x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);   x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);   x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);   x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);   return x; }