问题

给定范围 [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;
    }
}