「力扣」第 201 题:数字范围按位与

liweiwei1419 ... 2022-1-6 位运算
  • 位运算
Less than 1 minute

# 题目描述

给你两个整数 leftright ,表示区间 [left, right] ,返回此区间内所有数字 按位与 的结果(包含 leftright 端点)。

示例 1:

输入:left = 5, right = 7
输出:4
1
2

示例 2:

输入:left = 0, right = 0
输出:0
1
2

示例 3:

输入:left = 1, right = 2147483647
输出:0
1
2

提示:

  • 0leftright23110 \le left \le right \le 2^{31} - 1

分析:位运算的问题,干脆就把它记住。

思路:相邻的两个数末尾相与一定等于 00。于是就有如下写法:

Java 代码:

public class Solution2 {
    /**
     * 真的是很酷!
     *
     * @param m
     * @param n
     * @return
     */
    public int rangeBitwiseAnd(int m, int n) {
        int count = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            count++;
        }
        return m << count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

于是我们可以一步到位,利用 n &= (n - 1) 运算依次消去“大于” m 的部分的 11

Java 代码:

/**
 * https://blog.csdn.net/DERRANTCM/article/details/47997613
 *
 * @author liwei
 * @date 18/6/29 下午9:37
 */
public class Solution3 {

    /**
     * 利用了 n &= (n - 1) 一下能消死一大片
     *
     * @param m
     * @param n
     * @return
     */
    public int rangeBitwiseAnd(int m, int n) {
        while (n > m) {
            n &= (n - 1);
        }
        return n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Last update: January 14, 2022 00:24
Contributors: liweiwei1419