LeetCode 190 Reverse Bits 完整解析

將 32 位無符號整數的位元順序完全反轉（bit 0 ↔ bit 31, bit 1 ↔ bit 30, ...）。

方法一：分治合併法（最快、無分支）

以 16、8、4、2、1 為單位逐層交換，利用位元遮罩隔離區塊：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16);                    // 交換高低 16 位
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); // 交換位元組
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); // 交換 4 位
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); // 交換 2 位
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); // 交換相鄰位
        return n;
    }
};

每步位移補零（無符號右移），遮罩確保只交換目標區塊。

方法二：兩兩交換法（直觀、易理解）

class Solution {
public:
    uint32_t swapBits(uint32_t n, int i, int j) {
        int lo = (n >> i) & 1;
        int hi = (n >> j) & 1;
        if (lo != hi) {
            n ^= (1u << i) | (1u << j); // 異或翻轉：0^1=1, 1^1=0
        }
        return n;
    }
    
    uint32_t reverseBits(uint32_t n) {
        for (int i = 0; i < 16; i++) {
            n = swapBits(n, i, 31 - i);
        }
        return n;
    }
};

利用異或性質：x ^ 1 = ~x，x ^ 0 = x。僅當兩位不同時翻轉。

方法三：查表法（大量查詢時最優）

預計算 0~255 所有 8 位反轉結果，查表組合：

class Solution {
    uint8_t table[256];
    bool inited = false;
    
    void init() {
        for (int i = 0; i < 256; i++) {
            uint8_t x = i, rev = 0;
            for (int j = 0; j < 8; j++) {
                rev = (rev << 1) | (x & 1);
                x >>= 1;
            }
            table[i] = rev;
        }
        inited = true;
    }
    
public:
    uint32_t reverseBits(uint32_t n) {
        if (!inited) init();
        return (table[n & 0xff] << 24) |
               (table[(n >> 8) & 0xff] << 16) |
               (table[(n >> 16) & 0xff] << 8) |
               (table[(n >> 24) & 0xff]);
    }
};

效能對比