leetcode筆記之Bitwise AND of Numbers Range解析

leetcode筆記之Bitwise AND of Numbers Range解析

一. 題目描述

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

二. 題目分析

給定一個范圍[m, n]，其中 0 <= m <= n <= 2147483647，返回范圍內所有整數的按位與，包括邊界m和n。比如給定范圍為[5, 7], 應返回4。

單看題目描述，可以知道該題涉及到位運算，因此需動筆分析：

對於題目給定的范圍[5， 7]，可寫為：

5: 101
6: 110  -> 100 -> 4
7: 111

再來兩個例子：

范圍[6, 8]：

6: 0110
7: 0111  -> 0000 -> 0
8: 1000

范圍[8, 10]：

8:  1000
9:  1001  -> 1000 -> 4
10: 1010

現在可以總結出規律了，對於范圍[m, n]，若n的最高有效位比m的最高有效位要高，則必然會出現像例子出現的情況，必然在范圍內存在兩個數，這兩個數分別是對方的反碼：

6: 0110
7: 0111  -> 0000 -> 0
8: 1000

因此，只有當m和n的最高有效位一致時，即m與n同時右移n位，且m == n，m == 1時按位與結果不為0，且該結果為m與n的公共左邊首部，以下給出簡單的代碼：

三. 示例代碼

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

四. 小結

該題是數學問題，用位運算即可快速解決，主要是要找出規律。