LeetCode201-数字范围按位与

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/bitwise-and-of-numbers-range/

中文链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/

题目详述

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

示例 1: 

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

示例 2:

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

题目详解

  • 因为是在 [m, n] 的范围进行 & 运算，对于某个二级制位为 0，最终结果的那一位也为 0。

  • 例如对于 [26, 30]，二进制位如下：

  • 1
    2
    3
    4
    5
    11010
    11011
    11100　　
    11101　　
    11110

  • 所以问题的关键是找到高位相同的二进制位，当某一位不同时，从这一位开始到最低位，在给定范围内，必然存在在这一位上为 0 的数。

  • 找到 m 和 n 的二进制位中从高位到低位第一次不同的位置，在这个位置之前的二进制位所代表的数就是结果。

方法一：

  • 逐步去掉低位直到二者相等，得到高位，并记录移动的位数。
  • 最终左移回去即可。
1
2
3
4
5
6
7
8
9
10
11
12
public class LeetCode_00201 {

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

方法二：

  • 逐步去掉 n 的二进制位的最后一个 1，直到 m 不小于 n。
  • 此时 n 就是结果。
1
2
3
4
5
6
7
8
9
public class LeetCode_00201 {

    public int rangeBitwiseAnd(int m, int n) {
        while (m < n) {
            n &= n - 1;
        }
        return n;
    }
}