# 【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++`