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)
whereN
is the number of numbers betweenleft
andright
. This is2**31-1
, which will go out of limits. - Space:
O(1)
since we are only storing theans
.
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 theans
in solution 1 and 2 and nothing in solution 3
Thanks for reading!
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022