Bitwise AND of Numbers Range

Problem Statement

Given two integers left and right which represent the start and end of a numeric range [left, right], the task is to compute the bitwise AND operation for all integers between left and right, inclusive of left and right themselves. Bitwise AND is a binary operation that takes two bits at corresponding positions in the binaries of two numbers and yields 1 if both bits are 1, otherwise 0. For the range [left, right], we must apply this operation sequentially over all the numbers from left to right.

Examples

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

Constraints

• 0 <= left <= right <= 231 - 1

Approach and Intuition

1. Understand how bitwise AND operation works:

   • Given two numbers, bitwise AND operation is performed at the bit-level, aligning the numbers by their least significant bits.
   • For each pair of bits in the aligned positions, if both bits are 1, the result for that bit position is 1; otherwise, it is 0.

2. Recognize the problem with expansive ranges:

   • If right is significantly larger than left, the number of operations can grow large, making a direct computation inefficient.
   • For wide ranges, particularly when they across power of two boundaries, the result approaches 0 because the higher order bits diverge and do not satisfy the AND condition of being 1 simultaneously.

3. Implementation insights from examples:

   • Example 1 (left = 5, right = 7): Direct computational approach yields the result efficiently since the range is small. The bitwise AND of 5 (101_2), 6 (110_2), and 7 (111_2) results in 4 (100_2).
   • Example 2 (left = 0, right = 0): With only one number in the range, the result is the number itself, as there is no other number to AND with.
   • Example 3 (left = 1, right = 2147483647): Given the maximum possible range of integers, the result converges quickly towards zero, because it is improbable for all bits across such a vast range to be 1 simultaneously.

4. Optimal strategy:

   • Observe that the result is mainly dependent on the common leftmost bits of left and right.
   • Shift both left and right rightwards until they are equal. Each shift represents a lose of a differing bit starting from the least significant bit.
   • Once they are equal, shifting the result leftwards by the same number of shifts gives the final result. This left shift sets the lost varying bits to zero, which aligns with the behavior of the AND operation across the specified range.

Solutions

class Solution {
public:
    int bitwiseAndOfRange(int low, int high) {
        while (low < high) {
            high = high & (high - 1);
        }
        return high;
    }
};