Problem: 201. 数字范围按位与
基本思路
根据与运算的性质,只要区间 内的任意数在某一位出现 ,那么该位的最终结果为 。
从 的过程,二者的公共前缀肯定不会变化。
设非公共前缀分别为序列 ,。
对于 : 成立;
对于 :
- 若 ,由于需要为 或 进 ,故 区间必有一个数使得 成立;
- 若 ,则 成立。
可据此推广到剩余序列 ,。
根据上述分析可知,最终结果的非 部分只可能来自二者的公共前缀。
解题方法
通过异或运算
diff = left ^ right
,二者的公共前缀长度即为 diff
变量的最长前缀 的长度。故只需将 diff
向左移动直到 diff == 0
成立时的最小偏移量 shift
即为非公共前缀的长度。最终利用掩码 0xffffffff << shift
& right
即得到结果。Java
class Solution { public int rangeBitwiseAnd(int left, int right) { int diff = left ^ right; int shift = 0; while (diff != 0) { shift++; diff >>= 1; } return right & 0xffffffff << shift; } }
Python3
def rangeBitwiseAnd(left: int, right: int): diff = left ^ right shift = 0 while diff != 0: shift += 1 diff >>= 1 return right & 0xffffffff << shift
TypeScript
var rangeBitwiseAnd = (left: number, right: number) => { let diff: number = left ^ right; let shift: number = 0; while (diff != 0) { shift++; diff >>= 1; } return right & 0xffffffff << shift; }
JavaScript
var rangeBitwiseAnd = (left, right) => { let diff = left ^ right; let shift = 0; while (diff != 0) { shift++; diff >>= 1; } return right & 0xffffffff << shift; }
C#
public class Solution { public int RangeBitwiseAnd(int left, int right) { int diff = left ^ right; int shift = 0; while (diff != 0) { shift++; diff >>= 1; } return right & 0xffffffff << shift; } }
C
int rangeBitwiseAnd(int left, int right) { int diff = left ^ right; int shift = 0; while (diff != 0) { shift++; diff >>= 1; } return right & 0xffffffff << shift; }
复杂度分析
- 时间复杂度: 。
- 空间复杂度: 。