Bitwise AND of Numbers Range Explained

Problem Statement

Given two integers left and right representing the inclusive range [left, right], compute the bitwise AND of all numbers in this range. The key insight is that bits that differ across the range will become 0 in the result, so the solution involves finding the common prefix of left and right. This problem tests your ability to optimize bitwise operations over a sequence.

Example

Input: left = 5, right = 7

Output: 4

Explanation: 5 = 101, 6 = 110, 7 = 111. The bitwise AND of 101 & 110 & 111 is 100 = 4.

Code

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.rangeBitwiseAnd(5, 7)); // 4
    }
}
            

def range_bitwise_and(left, right):
    shift = 0
    while left != right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift

# Example usage
print(range_bitwise_and(5, 7))  # 4
            

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

// Example usage
console.log(rangeBitwiseAnd(5, 7)); // 4
            

Explanation

• Initialize a counter shift to track the number of right shifts.
• While left and right are different, right-shift both by 1.
• Increment shift for each right shift.
• When left equals right, the common prefix of the binary representations is found.
• Left-shift the result by shift to restore the original bit positions.

Note