【LeetCode】 190. 颠倒二进制位

算法

以8比特为例，abcdefgh，每次运算交换“奇偶位”，即[badcfehg]→[dcbahgfe]→hgfedcba

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    unsigned reverseBits(unsigned n) const {
        n = n >> 1 & M1   | (n & M1)  << 1;
        n = n >> 2 & M2   | (n & M2)  << 2;
        n = n >> 4 & M4   | (n & M4)  << 4;
        n = n >> 8 & M8   | (n & M8)  << 8;
        // n = n >> 16 & M16 | (n & M16) << 16;

        return n >> 16 | n << 16;
    }
private:
    const uint32_t M1  = 0x55555555;  // 01010101010101010101010101010101
    const uint32_t M2  = 0x33333333;  // 00110011001100110011001100110011
    const uint32_t M4  = 0x0f0f0f0f;  // 00001111000011110000111100001111
    const uint32_t M8  = 0x00ff00ff;  // 00000000111111110000000011111111
    // const uint32_t M16 = 0x0000ffff;  // 00000000000000001111111111111111
};

复杂度分析

  • 时间复杂度：；
  • 空间复杂度：；