位操作應用#

LeetCode 191: Number of 1 Bits#

計算無號整數二進位中 1 的個數（Hamming Weight）。

解法一：逐位檢查#

走訪 32 位，用 mask 逐一檢查每位。

public int hammingWeight(int n) {
    int count = 0;
    int mask = 1;
    for (int i = 0; i < 32; i++) {
        if ((n & mask) != 0) count++;
        mask <<= 1;
    }
    return count;
}

時間複雜度：O(32) = O(1)

解法二：Brian Kernighan’s Algorithm#

利用 x & (x-1) 每次消除一個 1。

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

時間複雜度：O(k)，k 為 1 的個數

對於稀疏位元（1 很少），解法二更高效。例如 1000...0000 只需迴圈 1 次。

LeetCode 231: Power of Two#

判斷整數是否為 2 的冪次方。

核心觀察#

2 的冪次方的二進位特點：只有一個 1

2^0 = 1   → 0001
2^1 = 2   → 0010
2^2 = 4   → 0100
2^3 = 8   → 1000

解法#

public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

邏輯：

n > 0：排除負數和 0
(n & (n-1)) == 0：只有一個 1 時，消除後為 0

LeetCode 338: Counting Bits#

給定 n，返回 0 到 n 每個數的二進位 1 的個數。

動態規劃解法#

利用遞推公式：bits[i] = bits[i & (i-1)] + 1

public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
}

原理：i & (i-1) 的值比 i 小，且 1 的個數恰好少 1。利用已計算的結果推導當前值。

時間複雜度：O(n)

N 皇后的位運算優化#

傳統 N 皇后使用集合記錄攻擊範圍，位運算可大幅加速。

核心思想#

用整數的二進位位表示棋盤狀態：

0：可放置
1：被攻擊

關鍵程式碼#

def dfs(row, col, pie, na):
    if row >= n:
        count += 1
        return

    # 取得當前層所有可放位置（1 表示可放）
    available = ~(col | pie | na) & ((1 << n) - 1)

    while available:
        # 取最低位的 1（選一個位置）
        p = available & -available

        # 遞迴到下一層
        dfs(row + 1,
            col | p,           # 列限制
            (pie | p) << 1,    # 左對角線向左移
            (na | p) >> 1)     # 右對角線向右移

        # 處理下一個可用位置
        available &= (available - 1)

位運算邏輯詳解

取得可用位置：

col | pie | na    → 所有被攻擊的位置（1 表示不可放）
~(...)            → 取反，變成可放位置
& ((1<<n) - 1)    → 只保留 n 位（遮罩）

選擇位置：

p = available & -available  → 取最低位的 1

更新攻擊範圍：

(pie | p) << 1  → 左對角線在下一行向左偏移
(na | p) >> 1   → 右對角線在下一行向右偏移

移除已處理位置：

available &= (available - 1)  → 清除最低位的 1

複雜度優勢#

方法	查詢複雜度	空間複雜度
集合/陣列	O(n)	O(n)
位運算	O(1)	O(1)

位運算解法在面試中能展現亮點，但必須能清楚解釋每一步的含義。死記硬背而無法解釋反而會被扣分。

練習題目#

題號	題目	難度
191	Number of 1 Bits	Easy
231	Power of Two	Easy
338	Counting Bits	Easy
136	Single Number	Easy
52	N-Queens II	Hard