题目链接：Reverse Bits

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

这道题的要求是反转32位整数的每一位。

  1. 按位处理

其实就是每次从右往左取出每一位，然后从左到右放进去即可。

时间复杂度：O(n)（n为位数）

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11

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

  1. 优化一下

而题目又进一步说如果该函数可能被频繁的调用好多次，怎么进行优化。。。像是上面的32次循环取位的代码应该不是很好了。。。

假设反转8位：12345678

  • 第1步：56781234
  • 第2步：78563412
  • 第3步：87654321

这样就在无需循环的情况下反转过来了。

因此，在对于32位的整数，先16位对换，然后是8位对换、4位对换、2位对换、1位对换即可

时间复杂度：O(logn)（n为位数）

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution
{
public:
    uint32_t reverseBits(uint32_t n)
    {
        n = n >> 16 | n << 16;
        n = (n & 0xFF00FF00) >> 8 | (n & 0x00FF00FF) << 8;
        n = (n & 0xF0F0F0F0) >> 4 | (n & 0x0F0F0F0F) << 4;
        n = (n & 0xCCCCCCCC) >> 2 | (n & 0x33333333) << 2;
        n = (n & 0xAAAAAAAA) >> 1 | (n & 0x55555555) << 1;
        return n;
    }
};