7
LeetCode 第 201 号问题：数字范围按位与
source link: https://www.cxyxiaowu.com/6922.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode 第 201 号问题：数字范围按位与-五分钟学算法
当前位置：五分钟学算法 > LeetCodeAnimation > LeetCode 第 201 号问题：数字范围按位与
本文首发于公众号「五分钟学算法」，是图解 LeetCode 系列文章之一。
题目来源于 LeetCode 上第 号问题：。题目难度为 Medium，目前通过率为 39.1% 。
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7]
输出: 4
示例 2:
输入: [0,1]
输出: 0
以 [ 26 ，30] 为例。
首先，将 [ 26 , 30 ] 的范围数字用二进制表示出来：
11010 11011 11100 11101 11110
而输出 24 的二进制是 11000 。
可以发现，只要找到二进制的 左边公共部分 即可。
所以，可以先建立一个 32 位都是 1 的 mask，然后每次向左移一位，比较 m 和 n 是否相同，不同再继续左移一位，直至相同，然后把 m 和 mask 相与就是最终结果。
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
unsigned int d = INT_MAX;
while ((m & d) != (n & d)) {
d <<= 1;
}
return m & d;
}
};
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK