Question
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.
Code
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
if (m == n) return m;
if (m == 0) return 0;
int i = 0;
while (m != n) {
m = m >> 1;
n = n >> 1;
i++;
}
return m << i;
}
}
Solution
仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，我们再来看一个范围[26, 30]，它们的二进制如下：
11010 11011 11100 11101 11110
发现了规律后，我们只要写代码找到左边公共的部分即可。
直接平移m和n，每次向右移一位，直到m和n相等，记录下所有平移的次数i，然后再把m左移i位即为最终结果
