題目： LeetCode - 201. Bitwise AND of Numbers Range

題目說明

給一個數值 m、一個數值 n，0 <= m <= n <= 2147483647。求 m & (m + 1) & ... & n 的值。

解題思路

對於 & 運算來說，只要有一個是 0，那結果就會是 0，所以我們只要看 m 跟 n 轉換成二進位後，以左而右從哪個數字開始不一樣，就從那個數字開始到最後面補 0 即可。
舉例來說：

1
2
3
4
5
5：00 00000 00000 00000 00000 00000 001|01
7：00 00000 00000 00000 00000 00000 001|11
                                        ^ 從這裡開始不一樣
所以答案是：
4：00 00000 00000 00000 00000 00000 001|00

做法也非常簡單，使用 >> 運算符，它會將數字轉換成二進位後，推掉最右邊的那一位，然後在最左邊補 0，而 >>= 的概念和 += 的概念是一樣的，例如：m >>= 1 等同於 m = m >> 1。所以我們只要一直對 m 和 n 一直做這種運算，直到兩者相等，最後再把右邊的 0 補回去即可。
※ << 和 >> 的作用一樣，只是它是把最左邊推掉，最右邊補 0。

參考解法

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int count = 0;
        while(m != n)
            m >>= 1, n >>= 1, ++count;
        return m << count;
    }
};