题目描述

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

样例

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

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

算法分析

• 1、求[m, n]的按位与，首先对于n和m这两个数在第i位前面都相同，由于n > m，因此n的第i位是1，m的第i位是0,即n = xxx1...，m = xxx0...，(...表示后面是什么未知)，因此一定会存在一个数是t = xxx1000的形式，即这个数的第i位是1，且后面的都是0的形式，并且这个数t一定在[m,n]内
• 2、这样的话[m,n]中的所有数与t按位与后再第i位以至后面全是0，因此只需求两个数的公共前缀即可。

时间复杂度 $O(1)$

Java 代码

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int res = 0;
        for(int i = 30;i >= 0;i --)
        {
            if((m >> i & 1) != (n >> i & 1)) break;
            if((m >> i & 1) == 1) res += 1 << i;
        }
        return res;
    }
}