Bitwise AND of Numbers Range

1. Initialize result with the value of left
2. Iterate from left + 1 to right:
   • Update result = result & current_number
   • If result becomes 0, break the loop (optimization)
3. Return result

In this approach, we iterate through all numbers from left to right and perform a bitwise AND operation on each number with the result of previous operations.

1public int rangeBitwiseAnd(int left, int right) {2    int result = left;3    for (int i = left + 1; i <= right; i++) {4        result &= i;5        // If result becomes 0, any further AND operations will remain 06        if (result == 0) {7            break;8        }9    }10    return result;11}

This approach works correctly for small ranges, but it will time out for large ranges like [1, 2147483647] because we would need to perform billions of operations.

1. Initialize a counter shift to 0
2. While left is less than right:
   • Right shift both left and right by 1
   • Increment shift by 1
3. Return left left-shifted by shift

The key insight is that if we perform a bitwise AND of all numbers in a range [left, right], the result will have 1s only at bit positions where all numbers in the range have 1s.

If left and right have different bit lengths or differ at any bit position, all numbers between them will have at least one number with a 0 at that position, making the AND result 0 at that position.

The result is essentially the common prefix of the binary representations of left and right, followed by zeros.

1public int rangeBitwiseAnd(int left, int right) {2    int shift = 0;3    4    // Find the common prefix by right shifting both numbers5    while (left < right) {6        left >>= 1;7        right >>= 1;8        shift++;9    }10    11    // Shift back to get the final result12    return left << shift;13}

This approach efficiently finds the common prefix of the binary representations of left and right, which is the result of the bitwise AND of all numbers in the range.

1. If left is 0, return 0 (optimization)
2. While right is greater than left:
   • Update right = right & (right - 1) (removes the rightmost set bit)
3. Return right

Brian Kernighan's algorithm is typically used to count set bits, but we can adapt it to solve this problem efficiently. The key insight is the same as the bit shifting approach - we need to find the common prefix of left and right.

Instead of shifting bits, we can directly remove the rightmost differing bit of right until it becomes less than or equal to left.

1public int rangeBitwiseAnd(int left, int right) {2    // If left is 0, the result will always be 03    if (left == 0) {4        return 0;5    }6    7    // Keep removing the rightmost set bit of right until right <= left8    while (right > left) {9        // Remove the rightmost set bit10        right = right & (right - 1);11    }12    13    return right;14}

This approach efficiently finds the common prefix by removing the rightmost differing bits, which is equivalent to finding the bitwise AND of all numbers in the range.