给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7] 输出: 4示例 2:
输入: [0,1] 输出: 0
解法一：
//时间复杂度O(1), 空间复杂度O(1)
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int diff = n - m;
int res = INT_MAX, mask = 1;
for(int i = 0; i < 31; i++) {
if(diff >= mask) res &= ~mask;//0
else res &= (m & n & mask) | ~mask;
mask <<= 1;
}
return res;
}
};//时间复杂度O(1), 空间复杂度O(1)
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
if(m == 0) return 0;
while(n > m) n &= n - 1;
return n;
}
};解法一：
假设int的二进制位的最低位为第0位，最高符位是第31位，符号位是第32位。
解题核心想法是，对于数字中的任意一位i（0 <= i <= 30），如果m和n之差大于等于2^i，那么在整数序列[m, n]的二进制表示的第i位中，必定至少有一处反转（1转为0或0转为1），那么连续按位与的结果必然是0。例如在序列[5, 6]中，差为1等于2^0，那么从5到6这个过程中，二进制表示的0位必然会反转。
其二是，如果m和n之差小于2^i，那可能反转，也可能不反转。此时取m和n该位的与作为该位的结果（如果反转，那m和n在该位上必然不同）。
解法二：
更简洁的解法。n &= n - 1;这一步的作用是将n最低位的1置0。可以这样理解，从m到n的序列中，这一组数字的二进制位表示可以分为两部分，相同前缀部分和不同的后缀部分（如 1011 0100 和 1011 0110，它们的公有前缀是101101，各自的后缀分别是00、10，也就是说后缀从首个不相同的位开始），区分它们之间大小关系只在于其后缀部分。由于这个序列是连续的整数，所以后缀的首位反转也意味着其后的所有位都有反转，所以后缀取与必然全为0，而前缀又全部相同，所以最后的答案一定是公有前缀 + 后缀等长的0序列，也就是满足 n <= m 时的n。
2020/01/08 23:43