Description:

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.

Link:

https://leetcode.com/problems/bitwise-and-of-numbers-range/description/

解題方法：

這道題最簡單的無非是暴力破解，但是這么簡單的方法肯定會超時，所以需要從其他方面找突破口：
舉個例子：當m = 5, n = 8時，把它們轉(zhuǎn)成二進制觀察：
5: 0101 6: 0110 7: 0111 8: 1000
我們可以看到當m和n不屬于同一個2^x級別時，從m到n的每個數(shù)在每一位都會有0，所以它&的結(jié)果必定為0，所以我們可以從左往右尋找m和n是否有在同一位置上的第一個1，如果沒有，結(jié)果肯定為0；如果有，則把這個1去掉進入下一次查找。

Time Complexity：

O(log(n))

完整代碼：

int rangeBitwiseAnd(int m, int n) 
    {
        int i = 1 << 30;
        while((i & m) == 0 && (i & n) == 0 && i >= 1)
            i >>= 1;
        if((i & m) != 0 && (i & n) != 0)
            return i + rangeBitwiseAnd(m - i, n - i);
        else
            return 0;    
    }