# 0201. 数字范围按位与

## 题目地址(201. 数字范围按位与)

<https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/>

## 题目描述

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

示例 1: 

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

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

## 前置知识

* 位运算

## 公司

* 阿里
* 腾讯
* 百度
* 字节

## 思路

一个显而易见的解法是， 从 m 到 n 依次进行`求与`的操作。

```javascript
let res = m;
for (let i = m + 1; i <= n; i++) {
  res = res & i;
}
return res;
```

但是， 如果你把这个 solution 提交的话，很显然不会通过， 会超时。

我们依旧还是用 trick 来简化操作。 我们利用的性质是， n 个连续数字求与的时候，前 m 位都是 1.

举题目给的例子：\[5,7] 共 5， 6，7 三个数字， 用二进制表示 101, 110,111, 这三个数字特点是第一位都是 1，后面几位求与一定是 0.

再来一个明显的例子：\[20, 24], 共 20， 21， 22， 23，24 五个数字，二进制表示就是

```
0001 0100
0001 0101
0001 0110
0001 0111
0001 1000
```

这五个数字特点是第四位都是 1，后面几位求与一定是 0.

因此我们的思路就是， 求出这个数字区间的数字前多少位都是 1 了，那么他们求与的结果一定是前几位数字，然后后面都是 0.

## 关键点解析

* n 个连续数字求与的时候，前 m 位都是 1
* 可以用递归实现， 个人认为比较难想到
* bit 运算

代码：

```javascript
n > m ? rangeBitwiseAnd(m / 2, n / 2) << 1 : m;
```

> 每次问题规模缩小一半， 这是二分法吗？

## 代码

语言支持：JavaSCript，Python3

JavaScript Code:

```javascript
/*
 * @lc app=leetcode id=201 lang=javascript
 *
 * [201] Bitwise AND of Numbers Range
 *
 */
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var rangeBitwiseAnd = function (m, n) {
  let count = 0;
  while (m !== n) {
    m = m >> 1;
    n = n >> 1;
    count++;
  }

  return n << count;
};
```

Python Code:

```python
class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        cnt = 0
        while m != n:
            m >>= 1
            n >>= 1
            cnt += 1

        return m << cnt
```

**复杂度分析**

* 时间复杂度：最坏的情况我们需要循环 N 次，最好的情况是一次都不需要， 因此时间复杂度取决于我们移动的位数，具体移动的次数取决于我们的输入，平均来说时间复杂度为 $O(N)$，其中 N 为 M 和 N 的二进制表示的位数。
* 空间复杂度：$O(1)$


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/201.bitwise-and-of-numbers-range.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.