Skip to main content

201. Bitwise AND of Numbers Range

hardAsked at AMD

Find the bitwise AND of all numbers in the range [left, right]. AMD asks this as a pure bit-manipulation hard — the insight that AND of a range equals the common prefix of left and right in binary is directly tied to address-range masking, subnet mask computation, and MMIO region overlap detection in hardware driver code.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates report Bitwise AND of Numbers Range as a hard problem specific to AMD's hardware-oriented interview culture, appearing in driver and firmware SWE rounds.
  • Blind (2025-10)— AMD interview threads flag this as a distinctive bit-manipulation hard that separates hardware-aware candidates, seen more at AMD than at pure SaaS companies.

Problem

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

Examples

Example 1

Input
left = 5, right = 7
Output
4

Explanation: 5=101, 6=110, 7=111. AND=100=4.

Example 2

Input
left = 0, right = 0
Output
0

Explanation: Single value 0.

Example 3

Input
left = 1, right = 2147483647
Output
0

Explanation: The range spans enough values to zero out all bits.

Approaches

1. Right-shift until equal (common prefix)

The AND of [left, right] equals the common binary prefix of left and right, padded with zeros. Right-shift both until they're equal, then shift back by the same count.

Time
O(log n) — at most 32 shifts
Space
O(1)
function rangeBitwiseAnd(left, right) {
  let shifts = 0;
  while (left !== right) {
    left >>= 1;
    right >>= 1;
    shifts++;
  }
  return left << shifts;
}

Tradeoff: O(32) = O(1). Elegant and branchless. The key insight: if any bit position differs between left and right, that bit must be 0 in the AND of the full range (because there exists a number in the range that toggles it).

2. Brian Kernighan bit-clearing on right

Repeatedly clear the lowest set bit of right (right &= right-1) until right <= left. This strips trailing bits that must be zero in the AND.

Time
O(log n)
Space
O(1)
function rangeBitwiseAnd(left, right) {
  while (right > left) {
    right &= (right - 1); // clear lowest set bit of right
  }
  return right;
}

Tradeoff: O(number of set bits in right) iterations. Uses the Brian Kernighan bit-clearing trick. Slightly more elegant when right has few set bits; the right-shift approach is more uniform.

AMD-specific tips

This problem has direct hardware relevance at AMD. Memory-mapped IO region overlap uses the same common-prefix masking: a block of addresses shares the same high-order bits when their range fits within a power-of-two-aligned region. The answer is exactly the subnet mask for [left, right] expressed as a prefix mask. When presenting this, state the insight first: 'The AND of a range equals the common binary prefix of the two endpoints, because any bit that differs must toggle through 0 in the range.' Then write the code. AMD interviewers will often ask: 'What does this mean for address-space masking in a hardware driver?'

Common mistakes

  • Trying to AND every number in the range — O(n) for a range of up to 2^31, completely infeasible.
  • Using arithmetic right shift (>>) — in JS, >> preserves the sign bit. Since the problem allows values up to 2^31-1 (positive), >> is fine here, but mention the distinction.
  • Shifting left back by `shifts` and overflowing 32-bit — in JS numbers are 64-bit floats, so shifting up to 32 is safe, but mention this for C/C++ implementations.
  • Brian Kernighan approach: using right & (right-1) incorrectly — this clears the LOWEST set bit, not the highest. The correct stopping condition is right <= left.

Follow-up questions

An interviewer at AMD may pivot to one of these next:

  • How does this relate to computing a network subnet mask from an IP address range?
  • Reverse Bits (LC 190) — complement of this problem in terms of bit manipulation.
  • How would you compute the memory address alignment mask for a given MMIO region in a kernel driver?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does the AND of a range equal the common prefix?

If left and right differ at bit position k, then there exists a number in [left, right] with bit k = 0 and another with bit k = 1 (the range crosses a boundary at that bit). AND of any pair with different values at bit k is 0, so bit k in the result must be 0. Only bits that are identical in all numbers in the range (i.e., the common prefix bits) survive.

What if left == right?

No shifting occurs. The result is left (= right). The AND of a single-element range is the element itself.

Does this work for left = 0?

Yes. If left = 0 and right > 0, eventually right > 0 = left after some bit-clearing, and right &= right-1 eventually reaches 0. The result is 0, which is correct since 0 AND anything is 0.

Practice these live with InterviewChamp.AI

Drill Bitwise AND of Numbers Range and other AMD interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →