LeetCode 201: Bitwise AND of Numbers Range Solution in Python Explained

Problem Statement

In LeetCode 201: Bitwise AND of Numbers Range, you’re given:

• Two integers left and right where 0 ≤ left ≤ right ≤ 2³¹ - 1.
• Your task is to find the bitwise AND of all integers from left to right, inclusive.

The bitwise AND operation (&) compares each bit of two numbers, resulting in 1 only if both bits are 1. This differs from grid traversal problems like LeetCode 200: Number of Islands, focusing instead on bit manipulation across a range.

Constraints

• 0 ≤ left ≤ right ≤ 2³¹ - 1.

Examples

Let’s see some cases:

Copy codeInput: left = 5, right = 7
Output: 4
Explanation: 5 & 6 & 7 = 4
<ul>
<li>5 = 0101</li>
<li>6 = 0110</li>
<li>7 = 0111</li>
<li>AND = 0100 (4)</li>
</ul>

Copy codeInput: left = 0, right = 0
Output: 0
Explanation: Single number 0 & 0 = 0.

Copy codeInput: left = 1, right = 2147483647
Output: 0
Explanation: Range includes 1 (0001) to 2³¹-1 (1111...1), AND results in 0.

These examples show we’re finding the common bits across a range.

Understanding the Problem

How do we compute the bitwise AND of a range in Python? Take left = 5, right = 7. We need 5 & 6 & 7. A naive approach would loop through all numbers, performing AND operations, but for large ranges (e.g., 1 to 2147483647), that’s painfully slow—O(n) time, where n = right - left + 1. This isn’t a dynamic programming challenge like LeetCode 198: House Robber; it’s about bit patterns. Notice:

• 5 = 0101
• 6 = 0110
• 7 = 0111
• Result = 0100 (4).

The result retains bits common to all numbers. We’ll use: 1. Bitwise Common Prefix: O(1) time, O(1) space—our best solution. 2. Naive Bitwise AND: O(n) time, O(1) space—an alternative for small ranges.

Let’s explore the best solution.

Best Solution: Bitwise Common Prefix Approach

Explanation

The Bitwise Common Prefix approach leverages a key insight: the bitwise AND of a range is the common prefix of left and right in binary, with trailing zeros. Why? As numbers increase from left to right, differing bits get “flipped” to 0 in the AND operation. For example:

• 5 (0101) to 7 (0111): Bits differ at positions 1 and 2, so the result is 0100 (4).
• The common prefix is 01, followed by zeros.

The algorithm:

• Right-shift both numbers until they’re equal (finding the common prefix).
• Left-shift the result by the number of shifts to align it.
• Time: O(1) (max 32 shifts for 32-bit integers), Space: O(1).

Step-by-Step Example

Example 1: left = 5, right = 7

Goal: Return 4.

• Step 1: Initialize.
• left = 5 (0101), right = 7 (0111), shift = 0.
• Step 2: Find common prefix.
• left != right, shift both right:
• 5 >> 1 = 2 (0010), 7 >> 1 = 3 (0011), shift = 1.
• 2 != 3, shift again:
• 2 >> 1 = 1 (0001), 3 >> 1 = 1 (0001), shift = 2.
• 1 == 1, stop.
• Step 3: Shift back.
• Common value = 1, shift left by 2: 1 << 2 = 4 (0100).
• Output: 4.

Example 2: left = 16, right = 19

Goal: Return 16.

• Step 1:
• 16 (10000), 19 (10011), shift = 0.
• Step 2:
• 16 != 19:
• 16 >> 1 = 8 (01000), 19 >> 1 = 9 (01001), shift = 1.
• 8 != 9:
• 8 >> 1 = 4 (00100), 9 >> 1 = 4 (00100), shift = 2.
• 4 == 4, stop.
• Step 3:
• 4 << 2 = 16 (10000).
• Output: 16.

How the Code Works (Bitwise Common Prefix) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef rangeBitwiseAnd(left: int, right: int) -> int:
    # Line 1: Initialize shift counter
    shift = 0
    # Tracks number of right shifts (e.g., 0)

    # Line 2: Find common prefix by right-shifting
    while left != right:
        # Continue until numbers are equal
        left = left >> 1
        # Right shift left (e.g., 0101 >> 1 = 0010)
        right = right >> 1
        # Right shift right (e.g., 0111 >> 1 = 0011)
        shift += 1
        # Increment shift count (e.g., 1)

    # Line 3: Shift back to original position
    return left << shift
    # Left shift common value (e.g., 1 << 2 = 0100)

This concise solution efficiently finds the bitwise AND.

Alternative: Naive Bitwise AND Approach

Explanation

The Naive Bitwise AND approach computes the AND by iterating through the range:

• Start with result = left.
• AND each number from left + 1 to right.
• Return the result.

It’s intuitive but slow—O(n) time, where n = right - left + 1. For small ranges, it’s fine, but for 1 to 2147483647, it’s impractical.

Step-by-Step Example

For left = 5, right = 7:

• Step 1: result = 5 (0101).
• Step 2: result &= 6 (0110) → 0100 (4).
• Step 3: result &= 7 (0111) → 0100 (4).
• Output: 4.

How the Code Works (Naive)

Copy codedef rangeBitwiseAndNaive(left: int, right: int) -> int:
    result = left
    for i in range(left + 1, right + 1):
        result &= i
    return result

Complexity

• Bitwise Common Prefix:
• Time: O(1) – max 32 shifts.
• Space: O(1) – no extra space.
• Naive Bitwise AND:
• Time: O(n) – loops through range.
• Space: O(1) – just one variable.

Efficiency Notes

Bitwise Common Prefix is the best solution with O(1) time and space, ideal for all ranges. Naive Bitwise AND is only practical for tiny ranges due to its linear time complexity.

Key Insights

• Common Prefix: Bits that stay constant.
• Shifting: Aligns and isolates the prefix.
• AND Property: Differing bits become 0.

Additional Example

For left = 8, right = 10:

• Goal: 8.
• Binary: 8 (1000), 9 (1001), 10 (1010).
• Common Prefix: Shift until 1, shift back → 8.

Edge Cases

• left = right: Returns left (e.g., 0 & 0 = 0).
• left = 0, right > 0: Returns 0 (0 ANDs everything to 0).
• Max Range: 1 to 2³¹-1 → 0.

Both solutions handle these correctly.

Final Thoughts

LeetCode 201: Bitwise AND of Numbers Range in Python is a brilliant bit manipulation challenge. The Bitwise Common Prefix solution shines with its speed and elegance, while the Naive approach offers a simple alternative for small ranges. Want more? Try LeetCode 136: Single Number for XOR tricks or LeetCode 338: Counting Bits for bit counting. Ready to test your skills? Solve LeetCode 201 on LeetCode with left = 5, right = 7 (expecting 4)—crack the bitwise code now!