【LeetCode】 201. Bitwise AND of Numbers Range

Description

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

給一個範圍[m, n]且 0 <= m <= n <= 2147483647，回傳對所有該範圍的數字做位元運算AND的結果，範圍包含邊界。

Example:

Example 1:

Input: [5,7]
Output: 4


Example 2:

Input: [0,1]
Output: 0

Solution

• 我們先很直覺的把題目要做的事情打出來：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int ans = m;
        for(int i = m + 1; i <= n; i++)
            ans = ans & i;
        return ans;
    }
};

• 按下送出後我們發現在測資0 2147483647吃了TLE，原因也很明顯，因為其實看到0就知道結果為0，卻做了多餘的運算，導致時間太久。
• 因此讓我們觀察一下如何加速：以4~7為例子
  
• 可以發現，我們只要看頭尾就可以分析出答案。怎麼看呢？
• 連續的數字，它一定從最小位元開始變，變過第一位就變第二位…因此如果它最小位元一樣，代表他前一位也要是一樣的。
  
• 也就是說我們只需要從最大位元開始檢查，頭尾是否一樣：
  • 如果一樣，就將該位元放入答案。
  • 如果不一樣，輸出答案。
• 最後的問題是如何取出想要的位元呢？很簡單，使用位移<<即可。
  • 如果要取m的第3位，那就m & (1 << 2)就好了。

Code

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int ans = 0;
        for(int i = 31; i >= 0 ; i--)
        {
            if((m & (1 << i)) == (n & (1 << i)))
                ans += (m & (1 << i));
            else 
                break;
        }
        return ans;
    }
};

tags: LeetCode C++