Bitwise AND of Numbers Range: Common Prefix of Binary Representations

LeetCode Bitwise AND of Numbers Range (Problem 201) asks: given two integers left and right, return the bitwise AND of all numbers in the range [left, right] inclusive.

For example, when left = 5 and right = 7, you AND together 5, 6, and 7. The result is 4. The brute-force approach of iterating through every number in the range is too slow when the range is large. There is a much faster way.

The key insight: common binary prefix

Look at the binary representations of 5, 6, and 7:

The leftmost bit (bit 2) is 1 in all three numbers. The remaining bits vary across the range. When you AND all the numbers together, any bit position that has both a 0 and a 1 somewhere in the range will produce 0 in the result.

The only bits that survive the AND are the ones that stay the same across every number in the range. Those bits form the common prefix of left and right in binary.

Why is the common prefix of just left and right sufficient? Because left and right are the smallest and largest values in the range. If a bit position differs between them, then every possible combination of 0 and 1 appears at that position somewhere in the range. AND-ing a 0 and a 1 always produces 0.

The approach

Find the common prefix of left and right in binary:

1. Right-shift both left and right by 1 until they are equal
2. Count how many shifts you performed
3. Left-shift the common value back by that count

When left and right are equal, all the differing lower bits have been shifted away. What remains is the common prefix. Shifting it back to its original position gives you the final answer.

Python solution

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

Walkthrough: left = 5, right = 7

Let's trace through the algorithm. The answer should be 4, since 5 & 6 & 7 = 4.

After two right shifts, both left and right equal 1. That is the common prefix. Shifting 1 back left by 2 gives 1 << 2 = 4, which matches 5 & 6 & 7 = 4.

Complexity analysis

The while loop runs at most once per bit position. For 32-bit integers, that is at most 32 iterations. Each iteration does constant work (two right shifts, one comparison, one increment).

Building blocks

This problem decomposes into two reusable building blocks that CodeBricks drills independently:

Binary common prefix

The idea that AND-ing a range of consecutive integers preserves only the shared high-order bits. Recognizing that "AND across a range = common prefix" lets you skip the brute-force enumeration entirely. This pattern generalizes to any scenario where you need to find bits that remain constant across a contiguous range.

Bit shifting

Right-shifting to strip bits from the low end, left-shifting to restore them. These are the fundamental tools for isolating, extracting, and repositioning bit patterns. You use right shift to compare prefixes and left shift to reconstruct the result.

# Core pattern: find common prefix via right shift
shifts = 0
while left != right:
    left >>= 1
    right >>= 1
    shifts += 1
result = left << shifts

Once you can fluently apply prefix extraction and bit shifting, this problem becomes a direct application. You stop worrying about the AND mechanics and start seeing the common prefix immediately.

Edge cases

left equals right. When left == right, the range contains a single number. The while loop never executes, shifts stays at 0, and the function returns left unchanged. The AND of one number with itself is that number.

left is 0. If left is 0, the result is always 0. Zero AND-ed with anything is zero. The algorithm handles this naturally: after enough right shifts, both values reach 0 and become equal.

Range spans a power of 2. For example, left = 1 and right = 2147483647. The range includes every 32-bit integer, and the AND of all of them is 0. The algorithm shifts both values all the way down to 0 before they match, then 0 << 31 = 0.

From understanding to recall

The common prefix insight is easy to grasp once you see it. But in an interview, you need to recall the technique instantly. Remembering that "AND across a range = common prefix" and that "shift until equal, then shift back" is the implementation takes practice.

Spaced repetition builds that recall. You type the shift loop from scratch today, then again in a few days, then a week later. Each time, the pattern becomes faster to retrieve. When you encounter a bit manipulation problem that involves ranges or consecutive numbers, the common prefix idea will surface automatically.

Related posts

• Number of 1 Bits - Another bit manipulation problem. Uses n & (n - 1) to clear set bits one at a time, a different technique that complements the prefix extraction approach here.
• Single Number - Uses XOR cancellation to find the lone unpaired element. While this problem uses AND across a range, Single Number uses XOR across an array. Both exploit bitwise properties to avoid brute-force enumeration.