0201._Bitwise_AND_of_Numbers_Range.md

201. Bitwise AND of Numbers Range

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/bitwise-and-of-numbers-range/description/

内容描述

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4
Example 2:

Input: [0,1]
Output: 0

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

我们知道你从m一直&到n，那么m和n二进制位后面不一样的地方肯定都会变成0

譬如n = 101111，m = 101011，当中经过101100。
m & n抹除common prefix右边第一位上的1，中间经过那个数抹除所有更低位的1。

所以我们找到m和n的最长相同前缀，然后补齐二进制的32位（即往右边贴'0'）

自己写的一行版本！

import os
class Solution(object):
    def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        return int(os.path.commonprefix([bin(m)[2:].zfill(32), bin(n)[2:].zfill(32)])[::-1].zfill(32)[::-1], 2)

思路 2 - 时间复杂度: O(1)- 空间复杂度: O(1)******

别人的一行版本！

class Solution(object):
    def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        return self.rangeBitwiseAnd(m, n & n-1) if m < n else n

思路 - 时间复杂度: O(1)- 空间复杂度: O(1)******

bit移位操作版本

class Solution(object):
    def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        diff = 0
        while m != n:
            m >>= 1
            n >>= 1
            diff += 1
        return m << diff