Bitwise AND of Numbers Range

Problem: Bitwise AND of Numbers Range

The first idea is just do AND operation on all the numbers. But actually this will cause wrong answer on python. Besides, it is also too time-consuming. We will explain this through a simple example.

For number through 5 to 7:

It's clear that the last two bits cannot be AND to 1 since they are not all one. Which means, if the last bits of the start and end of the range differ more than 1, the last bit will never AND up to 1. We can use this property to ignore surely 0 bits and only consider those who can possibly AND to 1.

Code in Python:

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