# 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

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

### 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.