Bitwise AND of Numbers Range | Brian Kernighan | LeetCode | Solution Explained

201. Bitwise AND of Numbers Range. Would have been easy if we were allowed to iterate over all the values. But, we have to be smarter and think in terms of bits. Finally, we discuss how to use Brian Kernighan algorithm. Problem Link.

Brute force Solution (Time Limit Exceeded)

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        ans = left
        for i in range(left, right+1):
            ans &= i
            if not ans: return ans
        return ans

Complexity Analysis

• Time: O(N) where N is the number of numbers between left and right. This is 2**31-1, which will go out of limits.
• Space: O(1) since we are only storing the ans.

Observations

Since the question is in the terms of bits, it is a good idea to think in terms of bits. Let’s see what happens here:

We figure that if there is at least 1 zero in the specified column, the entire column results in the value 0. ONLY if all the values are the same – either 1s or 0s in the column, then we keep it as is. Let’s take a look at another example.

It looks as if we are looking for the first disagreement between the right and left values.

Solution 1. Bit Shift (Accepted)

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        ans = 0
        for bit in reversed(range(31)):
            if ((1 << bit) & left) == ((1 << bit) & right):
                ans |= ((1 << bit) & left)
            else:
                break
        return ans

Solution 2. Setting to 0s (Accepted)

Alternatively, we can go in the reverse direction and keep setting the ith bit 0, bit by bit – until left > right

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        bit = 0
        while left < right:
            right = right & ~(1 << bit)
            bit += 1
        return right

Solution 3. Brian Kernighan’s Algorithm (Accepted)

A smarter way to set the last set bit to zero is to do num & (num-1) since that is going to convert the 1 – the set bit to a 0. This way we are able to skip over some bits, making this approach a bit faster.

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right = right & (right - 1)
        return right

Complexity Analysis

• Time: O(1) since we have to go over 31 bits at maximum
• Space: O(1) since we are storing only the ans in solution 1 and 2 and nothing in solution 3

Thanks for reading!

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.