LeetCode 201 詳解：Bitwise AND of Numbers Range (範圍按位與)

題目描述

給定範圍 [m, n] (0 ≤ m ≤ n ≤ 2³¹-1)，返回該範圍內所有整數的按位與結果。

範例：[5,7] → 5&6&7 = 4 (101 & 110 & 111 = 100)

核心規律

觀察二進位：

5:  101
6:  110
7:  111
&:  100  = 4

結果等於 m 和 n 的公共左側前綴（高位），低位全為 0。

原因：範圍內必包含某位從 0 變 1 再變 0 的完整週期，導致該位及更低位按位與結果為 0。只有 m 和 n 高位完全相同的位才可能保持 1。

算法：公共前綴提取

不斷右移 m 和 n 直到相等，記錄右移次數 shift，最後左移回去：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        return m << shift;
    }
};

執行過程圖解

m=5 (101), n=7 (111)

返回 1 << 2 = 100 (4) ✓

替代寫法：Brian Kernighan 算法

反覆清除 n 的最低置位 1，直到 n ≤ m：

int rangeBitwiseAnd(int m, int n) {
    while (n > m) {
        n &= (n - 1);  // 清除最低位 1
    }
    return m & n;
}

原理：n 的最低位 1 代表某位在範圍內會翻轉，清除它模擬範圍縮小。

複雜度分析

• 時間：O(log n) — 最多 31 次循環（32 位整數）
• 空間：O(1)

關鍵點總結

1. 按位與運算的「遞減性」：擴大範圍結果單調不增（位只會從 1 變 0）
2. 公共前綴 = 所有數在該位上保持 1 的必要條件
3. 右移法直觀易懂；Kernighan 法操作次數等於 n 中 1 的個數，極快
4. 邊界：m=0 直接返回 0；m=n 返回 m

總結

LeetCode 201 是位運算規律題。核心洞察：範圍按位與 = 兩端點的公共高位前綴 + 低位全 0。右移法代碼極簡，Kernighan 法利用 n & (n-1) 清除最低位 1 技巧更優雅。掌握此類位運算規律對解決範圍位運算問題至關重要。