# BITWISE AND OF NUMBERS RANGE

Interesting LeetCode problem. The description of the problem is the following:

``````Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0
``````

So, there are at least 2 solutions to solve this problem (I'll write it down in my favorite programming language - Rust). First solution is simple, we will go from first number in range over the all presented numbers (last number is included)

``````9   -- |0|0|0|0|1|0|0|1|
10  -- |0|0|0|0|1|0|1|0|
11  -- |0|0|0|0|1|0|1|1|
12  -- |0|0|0|0|1|1|0|0|
``````
rust
``````    pub fn range_bitwise_and(m: i32, n: i32) -> i32 {
let mut res = m;
for i in m..=n {
res &= i;
}

res
}
``````

But imagine if we would have following boundaries: `m = 1` and `n = 2147483647`. Uhh, it would be very heavy operation. If we try it out, it will cost us near ~730ms (it's not a mistake, almost 1 second). Let's turn on our brain and try to optimize this solution. Let's remember how bitwise AND works: (Tap)

``````    0101 (decimal 5)
AND 0011 (decimal 3)
= 0001 (decimal 1)
``````

So, we get 1 bit set only if in both numbers bit is equal to 1, otherwise - bit will set to zero. Let's take a look at the `m = 9` and `n = 12` sequence presented earlier.

``````9   -- |0|0|0|0|1|0|0|1|
10  -- |0|0|0|0|1|0|1|0|
11  -- |0|0|0|0|1|0|1|1|
12  -- |0|0|0|0|1|1|0|0|
``````

Do you see that? 1-th column. Oh, I have an idea, 4-th bit is set to 1 in all numbers in that sequence. Good. So, if we found that common bit we could set it in the result number, because as we know, all other bits will be 0 during computation. Also, we know the size of the number from the description - 2147483647. 32 bits. With that knowledge we can iterate from 0 to 32 (exclusive) and try to make a RIGHT SHIFT operation until `m` is less that `n` (remember, by description, m is always less than n). Why? Because when `n` became less or equal than `m` it would mean that we find that common prefix (further will be only zeros), both numbers now have bit 1 in position 0. Why only 2 numbers in that sequence, first and last? Because if we find that prefix on fist and the last numbers it would mean that all bits before will be 0 during AND operation on whole sequence. Let's take a look at that sample:

``````9   -- 0 0 0 0 1 0 0 1
12  -- 0 0 0 0 1 1 0 0
``````

perform a right shift:

``````4 -- 0 0 0 0 0 1 0 0
6 -- 0 0 0 0 0 1 1 0
``````

m < n - moving forward

``````2 -- 0 0 0 0 0 0 1 0
3 -- 0 0 0 0 0 0 1 1
``````

m < n - moving forward

``````1 -- 0 0 0 0 0 0 0 1
1 -- 0 0 0 0 0 0 0 1
``````

Great, m is equal to n... What's next? We find a prefix (bit) which will be equal to 1. Now, we need to set this bit in result number. LEFT SHIFT TIME :) We performed 3 right shifts, so, let's perform 3 left shift operations on shifted `m` or `n` it doesn't matter. `0 0 0 0 0 0 0 1` << 3 = `0 0 0 0 1 0 0 0`. Result is 2 * 2 * 2 = 8

Let's see the Rust solution:

rust
``````    pub fn range_bitwise_and(m: i32, n: i32) -> i32 {
let mut shift = 0;
let mut mr = m;
let mut nr = n;

while mr < nr {
mr >>= 1;
nr >>= 1;
shift += 1;
}

nr << shift
}
``````

Done)