Bitwise AND of Numbers Range - Solution & Explanation

Problem Overview: Given two integers left and right, compute the bitwise AND of every number in the inclusive range [left, right]. A naive approach would AND each number sequentially, but large ranges make that too slow. The key observation: if any bit position changes within the range, that bit becomes 0 in the final result.

Approach 1: Bit-shift Reduction (O(log n) time, O(1) space)

This approach repeatedly right-shifts both left and right until they become equal. Every shift removes the least significant bit where differences may occur. Each time the values differ, the lower bits must eventually flip within the range, meaning they contribute 0 to the final AND result. Count how many shifts are performed, then left-shift the common value back by that amount to restore the shared prefix.

The insight: the final answer is simply the common binary prefix of left and right. All trailing bits become zero because the range includes numbers where those bits toggle. Since integers have at most 32 bits, the loop runs at most 32 iterations, making the runtime effectively constant. This method relies heavily on bit manipulation operations like >> and <<.

Approach 2: Prefix Matching (O(log n) time, O(1) space)

This method focuses directly on identifying the longest common binary prefix between left and right. Start from the most significant bit and compare positions while both numbers share the same value. Once a mismatch occurs, all remaining bits must be zero in the result because the range includes numbers with both 0 and 1 in those positions.

You can implement this by repeatedly clearing the lowest set bit of right using right = right & (right - 1) until right <= left, or by comparing prefixes through shifts. Both techniques rely on properties of bitwise operators and binary representation. The algorithm runs in at most the number of bits in the integer (around 32 for typical constraints), keeping time complexity logarithmic.

Recommended for interviews: Interviewers typically expect the bit-shift reduction approach. It demonstrates clear understanding of how ranges affect binary bits and avoids unnecessary iteration through the range. A brute-force AND across all numbers shows the basic idea but fails performance constraints for large ranges. Recognizing that the result equals the shared binary prefix shows strong understanding of bit manipulation patterns frequently tested in technical interviews.