Bitwise AND of Numbers Range

• Difficulty: Medium
• Topics: Bit Manipulation
• Link: https://leetcode.com/problems/bitwise-and-of-numbers-range/

Problem Description

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

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

Example 3:

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

Constraints:

• 0 <= left <= right <= 231 - 1

Solution

1. Problem Deconstruction (500+ words)

• Rewrite the Problem

  1. Technical: Given two non‑negative integers left and right with left ≤ right, compute the bitwise AND of every integer in the closed interval [left, right]. Formally, compute result = left & (left+1) & … & right, where & denotes the bitwise AND operation.
  2. Beginner: Imagine each number is written in binary (using only 0s and 1s). For each column (representing 1’s, 2’s, 4’s, etc.), look at all the numbers in the range. If every number has a 1 in that column, then the answer gets a 1 in that column; otherwise, it gets a 0. Your task is to find the final binary number.
  3. Mathematical: Let $[l, r]$ be an integer interval. For each bit position $k$ (where $0 \le k \le 31$), define the predicate $P_k(i) = \text{the } k\text{-th bit of } i \text{ is 1}$. The result is:

     $$\text{AND}(l, r) = \sum_{k=0}^{31} \left( \min_{i \in [l, r]} P_k(i) \right) \cdot 2^k$$

     Equivalently, if we denote the bitwise AND as $\bigwedge$, then:

     $$\bigwedge_{i=l}^{r} i = \left( \bigcap_{i=l}^{r} S_i \right)_{\text{bitset}}$$

     where $S_i$ is the set of bit positions set in $i$.

• Constraint Analysis

  • 0 ≤ left ≤ right ≤ 2³¹ – 1
    • This restricts the input to non‑negative 32‑bit signed integers. The maximum value is 2,147,483,647, which uses 31 bits (bits 0–30). Bit 31 (the sign bit) is always 0.
    • Limitations on solutions: A brute‑force iteration over the entire range could involve up to ~2×10⁹ numbers, making an O(n) solution impractical. Hence, we need an algorithm that runs in sublinear time, ideally O(log n) or O(1).
    • Hidden edge cases:
      1. Single‑element range (left == right): The result is simply left.
      2. Range includes zero: If left == 0, then the AND is 0 regardless of right (because 0 has no bits set). This provides an early exit.
      3. Large ranges: When right – left + 1 > 2^k for some k, the k‑th bit will not be constant across the interval, so that bit in the result will be 0. In fact, for sufficiently large ranges, the result becomes 0.
      4. Power‑of‑two boundaries: If the interval crosses a power‑of‑two boundary (e.g., from 3 to 4), the higher bits change, affecting the common prefix.

2. Intuition Scaffolding

• Generate 3 Analogies

  1. Real‑World Metaphor (Consensus Filter): Think of a committee where each member votes “yes” (1) or “no” (0) on a list of proposals (bit positions). A proposal passes only if every member votes yes. As the committee grows more diverse (wider range), fewer proposals achieve unanimous support. The result is the set of proposals that everyone approved.
  2. Gaming Analogy (Skill Intersection): In an RPG, characters gain abilities as they level up. The “common skills” for levels left through right are those that every character in that level range possesses. Higher‑level characters may unlock exclusive skills, so the common set shrinks as the level range widens.
  3. Math Analogy (Periodic Bit Functions): Each bit position $k$ behaves like a square wave with period $2^{k+1}$: it stays 1 for $2^k$ consecutive numbers, then 0 for $2^k$ numbers, and so on. The AND asks whether the interval $[l, r]$ lies entirely within a “1” block. If the interval spans more than half a period ($>2^k$), the bit must be 0 in the result.

• Common Pitfalls Section

  1. Brute‑force iteration: Attempting to AND every number sequentially will time out on large ranges (e.g., [1, 2147483647]).
  2. AND of endpoints only: left & right is not necessarily equal to the AND of the whole range (e.g., 5 & 7 = 5, but the correct answer for [5,7] is 4).
  3. Assuming bit constancy: If a bit is set in both left and right, it might still flip inside the interval (e.g., bit 2 in [4,8] is 1 at 4 but 0 at 8).
  4. Over‑optimizing with length: Thinking that if right – left + 1 ≤ 2^k then bit k must be 1 is incorrect; the interval could straddle a block boundary even if it is short.
  5. Ignoring the zero case: Forgetting that left = 0 immediately forces the result to 0, leading to unnecessary computation.

3. Approach Encyclopedia

Approach 1: Naïve Brute Force

• Pseudocode:

  function rangeBitwiseAnd(left, right):
      result = left
      for i = left+1 to right:
          result = result & i
          if result == 0:   # early exit
              break
      return result
  

• Complexity Proof:
  • Time: $O(n)$ where $n = \text{right} - \text{left} + 1$. In the worst case (e.g., [1, 2³¹‑1]), $n \approx 2.15 \times 10^9$, which is infeasible.
  • Space: $O(1)$, only a few variables.
• Visualization:

  Numbers: left, left+1, …, right
  Bits:    b₃₁…b₀
  AND accumulates: start with all 1s of left, each new number clears bits where it has 0.
  Eventually, after enough numbers, all bits may become 0.
  

Approach 2: Bit‑by‑Bit Checking

• Pseudocode:

  function rangeBitwiseAnd(left, right):
      result = 0
      for k in 0..31:
          mask = 1 << k
          # Check if the k‑th bit is 1 in every number of [left, right]
          if (left & mask) and (right & mask):
              # Determine if the interval lies entirely within one "1‑block"
              block_size = mask << 1   # 2^(k+1)
              if (left // block_size) == (right // block_size):
                  # left and right in same block, and block is an odd block (bit=1)
                  if ((left >> k) & 1) == 1:
                      result |= mask
      return result
  

• Complexity Proof:
  • Time: $O(32)$ = $O(1)$, since we examine each bit once.
  • Space: $O(1)$.
• Visualization:
  For each bit k, imagine the number line partitioned into blocks of size $2^{k+1}$:

  Bit k pattern: |0..0|1..1|0..0|1..1|...
  Block size: 2^(k+1)
  If left and right fall in the same odd block, bit k=1 in result.
  

Approach 3: Common Prefix (Optimal)

• Insight: The AND of a range keeps only the bits that are common to all numbers. These are exactly the prefix bits that remain unchanged from left to right. The lower bits, where left and right differ, will eventually take both 0 and 1, so their AND becomes 0.
• Pseudocode:

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

• Complexity Proof:
  • Time: $O(\log(\max(left, right)))$ because each iteration reduces the numbers by half. In practice, at most 31 iterations for 32‑bit integers.
  • Space: $O(1)$.
• Visualization:

  Example: left = 5 (101), right = 7 (111)
  Iteration 1: left=2 (10), right=3 (11), shift=1
  Iteration 2: left=1 (1),  right=1 (1),  shift=2
  Result: 1 << 2 = 4 (100)
  The common prefix "1" is kept, and two trailing zeros are added.
  

Approach 4: Brian Kernighan’s Trick

• Insight: Clearing the lowest set bit of right with right = right & (right‑1) progressively removes bits that cannot be part of the common prefix. Continue until right ≤ left.
• Pseudocode:

  function rangeBitwiseAnd(left, right):
      while left < right:
          right = right & (right - 1)
      return right
  

• Complexity Proof:
  • Time: $O(\text{number of set bits in right})$, at most 31.
  • Space: $O(1)$.
• Visualization:

  Example: left=5, right=7
  right=7 & 6 = 6 (110)
  right=6 & 5 = 4 (100)
  Now right=4 < left=5, stop. Result=4.
  

4. Code Deep Dive

Optimal Solution (Common Prefix Method)

def rangeBitwiseAnd(left: int, right: int) -> int:
    shift = 0                     # Tracks how many bits we have shifted off
    while left != right:          # Continue until left and right match
        left >>= 1                # Shift left right by one bit
        right >>= 1               # Shift right right by one bit
        shift += 1                # Increment shift counter
    return left << shift          # Reconstruct the common prefix

Line‑by‑Line Annotations

1. shift = 0 – Initializes a counter for the number of low‑bit positions that will become zero.
2. while left != right: – Loop until left and right become identical. At that point, we have found the common prefix.
3. left >>= 1 – Discard the least significant bit of left, effectively moving to the next higher bit.
4. right >>= 1 – Same for right.
5. shift += 1 – Record that we have discarded one more bit.
6. return left << shift – The common prefix (left) is shifted back left by shift bits, filling the discarded bits with zeros.

Edge Case Handling

• Example 1 (left=5, right=7):
  • Iteration 1: left=2, right=3, shift=1
  • Iteration 2: left=1, right=1, shift=2 → exit loop.
  • Return 1 << 2 = 4.
• Example 2 (left=0, right=0):
  • Loop condition false, return 0 << 0 = 0.
• Example 3 (left=1, right=2147483647):
  • After 31 shifts, both become 0, shift=31, return 0 << 31 = 0.
• Large range crossing power‑of‑two:
  • E.g., left=12 (1100), right=15 (1111): after shifts, left=3, right=3, shift=2, return 3<<2=12. Correct, since 12 & 13 & 14 & 15 = 12.

5. Complexity War Room

• Hardware‑Aware Analysis:
  The common prefix method executes at most 31 iterations, each consisting of a shift, compare, and increment. On a modern CPU, these are single‑cycle operations. The entire loop fits in the instruction cache, and the few variables reside in registers, making it extremely fast (~10 ns). Even for the worst‑case input (left=1, right=2³¹‑1), the loop runs 31 times, which is negligible.

• Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	$O(n)$	$O(1)$	9/10 (simple)	❌ Fails large $n$
Bit‑by‑Bit	$O(1)$	$O(1)$	7/10 (detailed)	✅ Acceptable
Common Prefix	$O(\log n)$	$O(1)$	9/10 (elegant)	✅ Recommended
Brian Kernighan’s	ParseError: KaTeX parse error: Expected 'EOF', got '#' at position 9: O(\text{#̲set bits})	$O(1)$	8/10 (clever)	✅ Good alternative

6. Pro Mode Extras

• Variants Section

  1. Bitwise OR of Numbers Range: Compute $\bigvee_{i=l}^{r} i$. Unlike AND, the OR sets a bit if any number in the range has that bit set. Solution: find the most significant bit where left and right differ, then set all lower bits to 1. Example: [4,6] → binary 100,101,110 → OR = 111.
  2. Bitwise XOR of Numbers Range: There is a known pattern: xor_from_0_to_n can be computed in O(1), then xor(l, r) = xor(0, l‑1) ^ xor(0, r).
  3. Multiple Transactions (LC 123): If asked to compute AND over multiple disjoint ranges, precompute prefix ANDs or use segment trees for range queries.

• Interview Cheat Sheet

  • First step: Acknowledge brute force is too slow for the given constraints.
  • Key insight: The result is the common prefix of left and right in binary, with trailing zeros.
  • Algorithm: Shift both numbers right until equal, then shift left by the same amount.
  • Complexity: $O(1)$ time, $O(1)$ space.
  • Test cases: [5,7] → 4, [0,0] → 0, [1, large] → 0, [12,15] → 12.
  • Mention early exit: If left == 0, return 0 immediately.