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

### Recommended Posts

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

##### Furthest Building You Can Reach | LeetCode | Solution Explained

January 20, 2022

##### Jump Game IV | LeetCode | Solution Explained

January 15, 2022