跳转至

LeetCode: 201. 数字范围按位与

1、题目描述

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

示例 1:

输入: [5,7]
输出: 4

示例 2:

输入: [0,1]
输出: 0

2、解题思路

​ 首先确定这样一个问题,肯定是不能一步一步计算的,应该如何算呢

​ 每个数字都是32位的,

  • 第0位的数字,他是重复的,每两个数字重复一次
  • 第1位数字,也是重复的,每4个数字重复一次
  • 第1位数字,也是重复的,每4个数字重复一次

举个例子

从0-20

00000000000000000000000000000000
00000000000000000000000000000001
00000000000000000000000000000010
00000000000000000000000000000011
00000000000000000000000000000100
00000000000000000000000000000101
00000000000000000000000000000110
00000000000000000000000000000111
00000000000000000000000000001000
00000000000000000000000000001001
00000000000000000000000000001010
00000000000000000000000000001011
00000000000000000000000000001100
00000000000000000000000000001101
00000000000000000000000000001110
00000000000000000000000000001111
00000000000000000000000000010000
00000000000000000000000000010001
00000000000000000000000000010010
00000000000000000000000000010011

从0到20,一共是 21个数,如果按位与,肯定是0

分析第0位,如果长度超过1,就会出现0,肯定是0

第1位,长度超过2,会出现0

第2位,长度超过4,出现0

以此类推,如果长度没有超过,就判断这两个数的当前位是不是都是1,如果是,这一位就是1

class Solution:
    def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        result = ""

        nums = n - m + 1
        for i in range(32):
            if nums > (2 ** i):
                result += '0'
            else:
                if n & (1 << i) != 0 and m & (1 << i) != 0:
                    result += '1'
                else:
                    result += '0'

        return int("".join(list(reversed(result))), 2)

​ 本来觉得这个思路还不错,不过运行太慢

​ 我们在来分析一下

​ 如果两个数,

11110000

11110101

这个范围的结果,实际上就是两个数高的,相等的位

只要将1111取出来就好了,剩下的置零

结果为11110000

如果是

00001111

11110000

高位没有相同的,结果就是

00000000

class Solution:
    def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """

        left_move = 0
        while n > m:
            n = n >> 1
            m = m >> 1
            left_move += 1

        return n << left_move