Bitwise AND of Numbers Range

1. Description

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

2. Example

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

3. Constraints

• 0 <= left <= right <= $2^{31}$ - 1

4. Solutions

Bit Operations

n = right
Time complexity: O(logn)
Space complexity: O(n)

class Solution {
public:
    int rangeBitwiseAnd(const int left, const int right) {
        int shift = 0;
        int i = left, j = right;
        while (i < j) {
            i >>= 1;
            j >>= 1;

            ++shift;
        }

        return i << shift;
    }
};