博客

题目描述

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

示例1：

输入：[5,7]

输出：4

示例2：

输入：[0,1]

输出：0

思路分析

按照题目的要求，如果逐个按位与，那么在 m 、n 范围较大的情况下，将会出现超时。

对题目中所给用例 [5,7] 按位与运算：

1、可以看到，5 和 7 二进制形式存在公共前缀 01 ，因此从 5 → 7 ，其前两位 01 是一直不变的，只有后两位一直在变化，从 01 → 11。

我们可以确定按位与的结果，前两位一定是 01。

2、根据公共前缀确定结果前两位为 01，接下来就要确定剩余部分按位与结果。

若存在剩余部分，剩余部分的表现形式一定是 0XXX →1XXX。举个极端的例子 01111111 → 10000000（相差仅为 1 ）。

根据与运算规律 0 & 0 = 0 0 & 1 = 0，可以知道，若当前位存在 0，那么最终与运算的结果也一定为 0 。

即使在最极端的情况下，剩余部分中每一位也一定存在 0 ，因此我们可以认定，剩余部分按位与结果一定为 0。

「方法一」

通过前面的分析，可以看出，这道题其实是在求 m 和 n 的二进制形式的公共前缀。

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

「方法二」

求 m 和 n 的公共前缀，实际上就是把 m 或 n 非公共部分的 1 都敲掉，这个结果，一定小于等于 m。即 res ≤ m ≤ n 。

不断敲掉 n 最后一位 1，若此时 n 恰好小于等于 m ，说明已经将非公共部分的 1 全部敲掉。

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        if (m == 0) return 0;
        while (n > m) {
            n &= n - 1;
        }
        return n;
    }
}

技术公众号：小猿君的算法笔记