201.bitwise-and-of-numbers-range.md

题目地址(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 依次进行求与的操作。

letres=m;for(leti=m+1;i<=n;i++){res=res&i;}returnres;

但是， 如果你把这个 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 运算

代码：

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

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

代码

语言支持：JavaSCript，Python3

JavaScript Code:

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

Python Code:

classSolution: defrangeBitwiseAnd(self, m: int, n: int) ->int: cnt=0whilem!=n: m>>=1n>>=1cnt+=1returnm<<cnt

复杂度分析

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