题目描述

颠倒给定的 32 位无符号整数的二进制位。

示例:

输入: 43261596
输出: 964176192
解释: 43261596 的二进制表示形式为 00000010100101000001111010011100 ，
     返回 964176192，其二进制表示形式为 00111001011110000010100101000000 。

进阶: 如果多次调用这个函数，你将如何优化你的算法？

我的解法——进制转换（AC）

先转为2进制，再转为10进制
时间复杂度O(n)，空间复杂度O(n)
Beat 2%

class Solution:
    # @param n, an integer
    # @return an integer
    def tenToTwo(self,x):
        res = []
        while(x > 0):
            res.append(x % 2)
            x = (x - x % 2) / 2
        res += [0] * (32 - len(res))
        return res
    
    def reverseBits(self, n):
        now = self.tenToTwo(n)
        res = 0
        for i in range(31,-1,-1):
            res += pow(2,31 - i) * now[i]
        return res

最优解法——位运算

用循环遍历各个位，然后将其放到合适位置。
这里需要注意的是运算符的优先级， “«” 和 “&” 的优先级都很低，所以要加括号，这个地方很容易出错。

uint32_t reverseBits(uint32_t n)
{
    uint32_t ret = 0;
    for(int i = 0; i < 32; i++)
    {
        ret = (ret << 1) + (n & 1);
        n = n >> 1;
    }
    return ret;
}

最优解法——位运算+查表法

将 32 位整数列举一遍，但是可以列举小一点的整数。

class Solution {
public:
    uint8_t reverseChar(uint8_t c)
    {
        const uint8_t table[16] = {0x0, 0x8, 0x4, 0xC, 0x2, 0xA, 0x6, 0xE, 0x1, 0x9, 0x5, 0xD, 0x3, 0xB, 0x7, 0xF};
        return (table[c & 0xF] << 4) + table[c >> 4];
    }
    uint32_t reverseBits(uint32_t n) {
        uint8_t * p = (uint8_t *)&n;
        uint32_t ret;
        uint8_t * q = (uint8_t *) &ret;
        q[0] = reverseChar(p[3]);
        q[1] = reverseChar(p[2]);
        q[2] = reverseChar(p[1]);
        q[3] = reverseChar(p[0]);
        return ret;
    }
};

参考答案

http://lib.csdn.net/article/datastructure/13683