Bitwise AND of Numbers Range — The Common Prefix Trick That Avoids Brute Force

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.

Constraints:

• 0 <= left <= right <= 2^31 - 1

Example 1:

Input:  left = 5, right = 7
Output: 4
Explanation: 5 & 6 & 7 = 0b101 & 0b110 & 0b111 = 0b100 = 4

Example 2:

Input:  left = 0, right = 0
Output: 0

Example 3:

Input:  left = 1, right = 2147483647
Output: 0
Explanation: The range spans 2^31 numbers, so every bit position toggles at least once.

Why This Problem Matters#

This problem is a beautiful demonstration of how a brute-force loop over [left, right] (potentially 2 billion iterations) collapses into a 32-step bit-shift loop once you see the right invariant. The insight — that AND across a range produces the common binary prefix of the endpoints — is exactly the kind of "step back and analyze" reasoning FAANG interviewers want to see.

Companies like Amazon, Google, and Microsoft use this question to filter for candidates who can convert numerical observations into bit-level structure. The trick reuses across problems: longest common prefix in an XOR trie, range XOR queries, and prefix AND/OR aggregations in segment trees.

The Core Insight#

Claim: AND of all integers in [left, right] equals the longest common binary prefix of left and right, padded with zeros.

Why? Consider any bit position b where left and right agree. If both have bit b set, the lowest number in the range with bit b clear would be the first number after left that flips bit b — but if every number from left to right keeps bit b set, then they share that bit (and all higher matching bits) as a common prefix.

Conversely, consider any bit position where left and right differ. Since the range crosses the boundary where that bit toggles, there must be some integer in [left, right] with that bit clear and another with that bit set — so the AND drops that bit to 0. Same argument applies to all lower bits: somewhere in the range, every lower bit also toggles.

Algorithm: repeatedly right-shift both left and right until they are equal — counting the shifts. The shared value is the common prefix. Shift back left by the count to restore zeros in the cleared positions.

Visual Dry Run#

Input: left = 5 (0101), right = 7 (0111).

Loop exits when left == right == 1. Shift back left by 2: 1 << 2 = 4.

Verify: 5 & 6 & 7 = 0101 & 0110 & 0111 = 0100 = 4. Match.

Larger example: left = 12 (1100), right = 15 (1111).

Common prefix 0011, shift back: 0011 << 2 = 1100 = 12.

Verify: 12 & 13 & 14 & 15 = 1100 & 1101 & 1110 & 1111 = 1100 = 12. Match.

Solution (Optimal)#

Python#

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        # Find the common binary prefix by right-shifting both until equal
        shift = 0
        while left != right:
            left >>= 1     # drop low bit of left
            right >>= 1    # drop low bit of right
            shift += 1
        # The shared value is the common prefix; shift back to original position
        return left << shift

Alternative using Brian Kernighan-style bit clearing:

class Solution2:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        # Repeatedly clear the lowest set bit of right until right <= left
        while left < right:
            right &= right - 1   # clears the lowest set bit of right
        return right

JavaScript#

var rangeBitwiseAnd = function(left, right) {
    // Common-prefix approach: right-shift both until they match
    let shift = 0;
    while (left !== right) {
        left >>>= 1;    // logical right shift to handle high bit cleanly
        right >>>= 1;
        shift++;
    }
    return left << shift;
};

Complexity: Time O(log(max)) = O(32) for 32-bit integers, Space O(1).

Common Mistakes#

1. Brute-forcing the AND loop. Computing result = left; for i in range(left+1, right+1): result &= i is O(right - left), which TLEs when the range is large.

2. Stopping the shift loop too early. The exit condition is left == right. Stopping when left == 0 or comparing differently misses the actual common prefix.

3. Using arithmetic right shift on signed integers in JavaScript. With >>, the sign bit replicates on negative values. Use >>> for logical (unsigned) right shift — this matters because the constraint allows up to 2^31 - 1, which is the boundary of 32-bit signed range.

4. Forgetting the final left-shift. The common prefix lives in the high bits; you must shift it back to its original position. Returning left (without << shift) yields an answer that is smaller by a factor of 2^shift.

5. Confusing this with range XOR. Range XOR has a different closed form using the cyclic pattern XOR(0, n) and parity. Don't apply that pattern here.

Interview Tips#

• Walk through a small example like [5, 7] on paper. Show how each bit toggles in the range and why low bits collapse to zero.
• State the invariant: "AND across a contiguous range equals the common high-bit prefix of the endpoints." This is the one sentence interviewers want to hear.
• Mention the Brian Kernighan alternative while left < right: right &= right - 1. It is often faster in practice and shows you know multiple bit tricks.
• If asked about overflow or huge ranges, note that the algorithm runs in 32 steps regardless — the size of the range does not affect runtime.

Follow-up Questions#

Q: Why does right &= right - 1 until right <= left give the same answer? Each right & (right - 1) clears the lowest set bit. As long as right > left, the lowest set bit of right lies in the variable region of the range, so the AND across the range must clear it. Once right <= left, no further clearing is justified.

Q: How would you compute range OR over [left, right]? OR is monotone non-decreasing as you add numbers, so range OR = highest power of 2 not exceeding right minus 1, then OR'd appropriately. Actually a simpler closed form: range OR is right | (right - 1) | ... until you exceed left — analogous shift-based logic.

Q: How would you compute range XOR? Use xor(0, n) = n, 1, n+1, 0 cycle pattern: prefixXor(n) based on n % 4, then prefixXor(right) ^ prefixXor(left - 1).

Q: What is the time complexity if right could be a 64-bit integer? Still O(log right) = O(64). The number of bits, not the magnitude of the range, drives runtime.

Key Takeaways#

• AND across a contiguous range collapses to the common high-bit prefix of left and right.
• Right-shift both until equal, count the shifts, then shift back — O(log max) = O(32) total.
• Equivalent Brian Kernighan form: clear the lowest set bit of right while right > left.
• Brute force O(range) is a trap; recognize the invariant before writing code.
• Use logical right shift (>>> in JavaScript) to handle the upper bound of 32-bit signed range.
• The common-prefix observation generalizes to range XOR, range OR, and trie-based range queries.