目录

0201:数字范围按位与(★)

力扣第 201 题

题目

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

示例 1:

输入:left = 5, right = 7
输出:4

示例 2:

输入:left = 0, right = 0
输出:0

示例 3:

输入:left = 1, right = 2147483647
输出:0

提示:

  • 0 <= left <= right <= 231 - 1

相似问题:

分析

  • 本题要利用位运算与的特性:
    • 假如 right 的二进制位数比 left 多,结果必然为 0
    • 假如位数相等,去掉 right 和 left 二进制的第一位,转为递归子问题
  • 因此只需要找到 right 和 left 的二进制表示的公共前缀,后面补 0 即可
  • 具体实现时有个巧妙的方法:
    • right 不断去掉最右边的 1 直到 right<=left,即为所求

解答

1
2
3
4
5
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while right>left:
            right &= right-1
        return right

46 ms