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.

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时，把它们转成二进制观察：
5: 0101 6: 0110 7: 0111 8: 1000
我们可以看到当m和n不属于同一个2^x级别时，从m到n的每个数在每一位都会有0，所以它&的结果必定为0，所以我们可以从左往右寻找m和n是否有在同一位置上的第一个1，如果没有，结果肯定为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;    
    }