leetcode (力扣) 201. 数字范围按位与 (位运算)

题目描述

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

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

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

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

思路分析

这道题是求left到right之间每一个数与操作的结果。

测试用例还挺良心的，给了个1-2147483647。告诉你暴力过不了哈哈。

这里可以回想一下二进制与操作，两个数的‘’与‘’只要有0则为0。
而一个数不断加1变成另一个数的过程中，实际上每一位都有变成0的情况。
这里举个例子秒懂，

• 比如4->5 对应二进制 101->110
• 9->10 对应二进制 111->1000
• 100->101 对应二进制 1100100 ->1100101

所以其实就是找两个数的最长公共前缀。

这样思路就简单了，两个数的二进制不断往右移动，当两者相等的时候，停止移动。
记t为移动的次数，t就是两个数的二进制不同的位数。此时再左移t位就可以啦。

完整代码

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        res = 0

        while left<right:
            left = left>>1
            right = right>>1
            res +=1
        return left<<res
        
        ```

1
2
3
4
5
6
7
8
9
10
11
12