链接
https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/
耗时
解题：1 h 21 min
题解：28 min
题意
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
思路
首先，如果 m 是 0，结果肯定为 0；如果 m == n，与完也应该是本身。
然后如果 n 的二进制位数 比 m 的二进制位数 多，那么肯定是 0，因为
00001xxxxxx // m 是这样的
00010000000 // 范围内必然存在这样的
这俩一与直接变成 0，所以结果必然是 0。
最后如果 m 和 n 的二进制位数是一样的（因为相同的情况已经判断完了，所以到这里 n 大于 m），可以找到 m 和 n 的二进制最高的相同位的一对 0 1，将这一位及它后面的所有位的数全变为 0，即是答案。因为既然位数相同，则必然高位的部分的数字应该是相同的（起码最高位的1应该是一样的），像这样
00001010110 `0` xxxxxxxxxx // m
00001010110 `1` 0000000000 // 范围内必然存在这样的
00001010110 `1` xxxxxxxxxx // n
那个范围内必然存在的数和 m 一与，最高位的一对 0 1 及其后面的数字就全是 0 了，并且高位的数字不会变，所以答案就是把最高位的 0 1 和它后面的数字全变成 0，保留相同的高位数字就是了。
时间复杂度：
O
(
l
o
g
n
)
O(logn)
O(logn)，n 的二进制位数
AC代码
class Solution {
public:
int number_binary_digit(int x) {
int res = 0;
while(x) {
res++;
x >>= 1;
}
return res;
}
int rangeBitwiseAnd(int m, int n) {
if(m == 0) return 0;
if(m == n) return m;
int num_m = number_binary_digit(m);
int num_n = number_binary_digit(n);
if(num_n > num_m) return 0;
int pos = 0;
for(int i = 0, tmp_m = m, tmp_n = n; tmp_m; tmp_m>>=1, tmp_n>>=1, ++i) {
int m1 = tmp_m&1;
int n1 = tmp_n&1;
if(m1 != n1) pos = i;
}
int ans = m;
ans >>= pos;
ans <<= pos;
return ans;
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
