# 201. Bitwise AND of Numbers Range

Question link is here.

# Question

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

# Solution

First, it's obvious that if right has more bit length than left, the answer would be 0. Because we are doing AND operation, for every number between left to right, there must be a least one "0" appeared in each bit.

Second, it left and right has the same bit length, we just need to find the common prefix of binary string of left and right. And than shift the common prefix to it's corrosponding position.

# Python

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shift = 0
        if left.bit_length() < right.bit_length():
            return 0
        flag = False
        while left < right:
            left = left >> 1
            right = right >> 1
            shift += 1
        return left << shift
   

# Java

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            left = left >> 1;
            right = right >> 1;
            shift += 1;
        }
        return left << shift;
    }
}

Time Complexity $O(n)$ for each operations.