201. 數字範圍按位與

思路

現在的右邊界是 $\text{right}$，跟 $\text{right - 1}\&$ 之後，$\text{right}$的最後一個 1 就會被捨棄。
找到 $\text{right}$最右邊的 $1$ 所在的位置。
然後減去這個數值，就能將無法活下來的位數給抹掉。

只有前面的 1 才有機會活下來，最後一個 1 已經沒有機會了。
重複操作直到 $\text{left}\geq\text{right}$，也就是讓 $\text{right}$無法再往下減。

程式碼

位運算

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        while(left < right) {
            right -= right & -right;
        }
        return right;
    }
};

複雜度分析

• 時間複雜度：$O(\log{n})$
• 空間複雜度：$O(1)$