给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。
示例 1:
输入: [5,7]
输出: 4
示例 2:
输入: [0,1]
输出: 0
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/bitwise-and-of-numbers-range
解题思路
与运算就是全部为1
才为1
,所以我们可以从n
开始,让n &= n - 1
直到n <= m
我们知道n &= n - 1
会让n
的最右边的1
直接变为0
,这样可以很快的提取出公共前缀
剩下最后的公共前缀就是按位与的结果
代码
class Solution {
public int rangeBitwiseAnd(int m, int n) {
while (n > m) {
n &= n - 1;
}
return n;
}
}