201. Bitwise AND of Numbers Range

Description

The problem is to find the bitwise AND of all numbers in a given range \([left, right]\). The bitwise AND operation is a binary operation that takes two equal-length binary representations and performs the logical AND operation on each pair of the corresponding bits, which results in a new binary number.

Intuition

The key observation is that the bitwise AND of a range of numbers is significantly affected by the common prefix in the binary representation of the numbers in that range. If there are differing bits at any position, the result of the AND operation will zero out those positions and all positions to the right.

Approach

1. Initialize a shift variable to 0. This will keep track of how many bits we need to shift to the right.
2. While left is not equal to right, right shift both left and right by 1, and increment the shift counter.
3. The above loop helps us to identify the common prefix of the binary representations of left and right.
4. Once we have the common prefix, left shift left by shift to restore it to its original bit length, but now with all differing bits zeroed out.
5. Return the result.

Complexity

Time Complexity:

(O(\log(\text{right}))) - In the worst case, we will shift the bits until left becomes equal to right, which is approximately the logarithm of right.

Space Complexity:

(O(1)) - We are using a constant amount of extra space.

Code

C++

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

Python

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shift = 0
        while left != right:
            left >>= 1
            right >>= 1
            shift += 1
        return left << shift

Java

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

JavaScript

var rangeBitwiseAnd = function (left, right) 
{
    var shift = 0;
    for (; left != right; left >>= 1, right >>= 1, shift++) { }
    return left << shift;
};