题目描述

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

示例 1:

输入: [5,7]
输出: 4
示例 2:

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

解法

  1. 位移

思路：暴力法肯定不用考虑了，数字很大时一定会超时🤒。最开始的思路是将范围内的数字一位一位的做与运算，最后一想和暴力法区别不大。看了官方题解，学到了位移法。

可以发现，由于与运算的特性是有0则0，所以m, n范围内的数字相与就是这两个数字的最长公共前缀，然后在后面补上相应的0即可。

8 12范围内按位与的结果为8

4 12范围内按位与的结果为0

步骤是这样的，判断m和n是否相等，如果不相等，m n均向右移一位，直到m n相等为止。记录下移动的位数，最终返回m左移移动的位数。

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 = m >> 1;
            n = n >> 1;
            shift++;
        }
        return m << shift;
    }
}

时间复杂度为$O(logn)$ 因为$m <= n$，所以取决于n的二进制数的位个数。
空间复杂度为$O(1)$ 使用了常数大小的额外空间。

参考