LeetCode 201. Bitwise AND of Numbers Range
题目描述
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: [5,7]
Output: 4
Example 2:
Input: [0,1]
Output: 0
解题思路
题目的意思很简单，就是给定两个端点m和n，求问闭区间内部所有数字的二进制与的值。
- 暴力方法是直接遍历做位运算，可能会超时；加入一个短路条件竟然也能AC：0和任何数做二进制与操作都是0。
- 观察发现，二进制运算的结果实质上就是尾部不断变动的0消除了后缀不同数字，最终得到的是二进制下m和n的最长公共前缀。
- 还可以进一步优化，消除尾部的1可以用
n & (n-1)来加速，最长公共后缀结果是尾部全0，满足res <= m <= n，那么我们一步一步消减n尾部的0，直到n <= m时得到的就是res。
参考代码
/*
* @lc app=leetcode id=201 lang=cpp
*
* [201] Bitwise AND of Numbers Range
*/
// @lc code=start
class Solution {
public:
/*
int rangeBitwiseAnd(int m, int n) {
int res = 0xFFFFFFFF;
int bkp = 0xFFFFFFFF; if(n==2147483647){bkp=n;n--;}
for (int i=m; i<=n; i++) {
res &= i;
if (res == 0) break; // fast fail
}
res &= bkp; // avoid i++ overflow
return res;
} // AC, brute force beats 5.43 % of cpp submissions
*/
/*
// bitwise longest common prefix
int rangeBitwiseAnd(int m, int n) {
int offset = 0;
while (m != n) {
m >>= 1;
n >>= 1;
offset++;
}
return n << offset;
} // AC, beats 44.2 % of cpp submission
*/
// bitwise longest common prefix
int rangeBitwiseAnd(int m, int n) {
// 0 <= m <= n <= 2147483647
while (m < n) {
n &= (n - 1);
}
return n;
} // AC
};
// @lc code=end