Bitwise And Of Numbers Range - Leetcode Solution

Problem Statement:

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

Input: left = 5, right = 7

Output: 4

Solution:

The simplest solution to this problem is to perform the bitwise AND operator on all of the numbers in the range between left and right, inclusive. Since the maximum range is 2147483647, it's not possible to perform a bitwise AND operation on so many numbers. Therefore, this solution is not efficient.

A better approach to solving this problem is to find the common bits between left and right. In other words, we need to find the position of the most significant bit that is set in left and right and count the number of bits from that position to zero. Once we count the number of bits, we shift the result of left to the right by the count value. This shifts the bits to the right and sets all the bits to the right of the most significant bit to zero. This is because we know that the bits to the right of the most significant bit will be zero in all the numbers within the range [left, right]. Finally, we return the shifted value of left.

Consider the example where left = 5 and right = 7. The binary representation of the numbers in the range [5,7] are:

101 (5)
110 (6)
111 (7)

We can see that all three numbers share the common bit at the most significant bit position. Therefore, we can set all the bits to the right of the most significant bit position to zero by shifting left to the right by the count of bits. In this case, the count is 1 because the most significant bit position is 2.

101 (5) -> 10 (2)
110 (6) -> 11 (3)
111 (7) -> 11 (3)

After shifting left to the right by 1 bit position, we get 100 (4). This is the result of the bitwise-AND operation of all the numbers in the range [5,7].

Code:

int rangeBitwiseAnd(int left, int right) { int count = 0;

while (left != right) {
    left >>= 1;
    right >>= 1;
    count++;
}

return left << count;

}

The time complexity of the above code is O(log n), where n is the maximum range of the input. This is because we perform bitwise shifting on the input, which takes O(log n) time. The space complexity of the code is O(1) because we don't use any additional data structures.

1