题目描述

请翻转一个32位无符号整数的所有二进制位。

进一步： 如果该函数会被调用多次，该如何优化？

样例

输入：43261596
输出：964176192
解释：43261596的二进制表示是00000010100101000001111010011100, 
      将其翻转后是00111001011110000010100101000000，
      表示的十进制数是964176192.

算法

(位运算) $O(1)$

使用位运算 n >> i & 1 可以取出 $n$ 的第 $i$ 位二进制数。
我们从小到大依次取出 $n$ 的所有二进制位，然后逆序累加到另一个无符号整数中。

时间复杂度分析：C++中所有位运算的计算量都是1，比如 n >> 10，将 $n$ 右移10位，计算量是1而不是10。所以在该问题中，我们总共进行了 4 * 32 次运算，所以时间复杂度是 $O(1)$。

C++ 代码

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; i ++ )
            res = (res << 1) + (n >> i & 1);
        return res;
    }
};