问题

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例1

1
2

输入: [5,7]
输出: 4

示例2

1
2

输入: [0,1]
输出: 0

思路

观察两个端点值m和n的二进制表示，如m=5，n=7，此时m=0101，n=0111，从m逐渐增加到n，前缀部分01XX后面的数位XX中的每一位都会出现一次0，导致这一位总体上与的结果为0。那么这个问题就可以转化为求两个二进制数的公共前缀。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while(m != n){
            m >>= 1;
            n >>= 1;
            shift++;
        }
        return m << shift;
    }
}