LeetCode_位运算_中等_201.数字范围按位与

水深无声 2023-10-12 16:59 14阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你两个整数 left 和 right ，表示区间 \[left, right\] ，返回此区间内所有数字按位与的结果（包含 left 、right 端点）。

**示例 1：**  
输入：left = 5, right = 7  
输出：4

**示例 2：**  
输入：left = 0, right = 0  
输出：0

**示例 3：**  
输入：left = 1, right = 2147483647  
输出：0

**提示：**  
0 <= left <= right <= 231 \- 1

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/bitwise-and-of-numbers-range

## 2.思路 ##

（1）一次遍历  
比较简单的方法是遍历区间 \[left, right\] 内的所有数，然后进行相与即可。但是该代码在 LeetCode 中提交会出现“超出时间限制”的提示！

（2）寻找公共前缀  
思路参考[本题官方题解][Link 1]。

（3）Brian Kernighan 算法  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int rangeBitwiseAnd(int left, int right) {
        
            int res = left;
            for (int i = left + 1; i <= right; i++) {
        
                res &= i;
            }
            return res;
        }
    }

//思路2————寻找公共前缀
    class Solution {
        
        public int rangeBitwiseAnd(int left, int right) {
        
            int shift = 0;
            //找到公共前缀
            while (left < right) {
        
                left >>= 1;
                right >>= 1;
                ++shift;
            }
            return left << shift;
        }
    }

//思路3————Brian Kernighan 算法
    class Solution {
        
        public int rangeBitwiseAnd(int m, int n) {
        
            while (m < n) {
        
                //抹去最右边的 1
                n = n & (n - 1);
            }
            return n;
        }
    }

[Link 1]: https://leetcode.cn/problems/bitwise-and-of-numbers-range/solution/shu-zi-fan-wei-an-wei-yu-by-leetcode-solution/