LeetCode 位運算三部曲：反轉位元、計算漢明重量、整數反轉

問題一：Reverse Bits（反轉 32 位無符號整數）

輸入 43261596 (二進制 00000010100101000001111010011100)，輸出 964176192 (00111001011110000010100101000000)。

基礎解法：逐位檢查構建

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

時間 O(32)，空間 O(1)。可優化為查表法（8位/16位預計算）提升常數因子。

問題二：Number of 1 Bits（漢明重量）

統計無符號整數二進制中 1 的個數。例：11 → 3。

巧解：Brian Kernighan 算法

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while (n) {
            n &= (n - 1);  // 消除最低位的 1
            ++cnt;
        }
        return cnt;
    }
};

循環次數等於 1 的個數，最佳情況 O(1)，最壞 O(32)。內建函數 __builtin_popcount 可單指令完成。

問題三：Reverse Integer（整數反轉）

反轉 32 位有符號整數數字，溢出返回 0。例：123 → 321，-123 → -321。

關鍵點：溢出檢測

class Solution {
public:
    int reverse(int x) {
        long long res = 0;  // 用 64 位暫存避免中間溢出
        while (x) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return (res < INT_MIN || res > INT_MAX) ? 0 : (int)res;
    }
};

或不使用 64 位，在乘法前預判：if (res > INT_MAX/10 || (res==INT_MAX/10 && pop>7)) return 0;。

位運算核心技巧總結

LeetCode 相關題目推薦

• 190. Reverse Bits
• 191. Number of 1 Bits
• 7. Reverse Integer
• 231. Power of Two
• 338. Counting Bits（DP + Lowbit）
• 371. Sum of Two Integers（位運算模擬加法）