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|

    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:

    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)