Skip to main content

201. Bitwise AND of Numbers Range

medium

Compute the bitwise AND of every integer in [left, right] inclusive. The trick: keep right-shifting both endpoints until they match — that's the common prefix.

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

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

Example 2

Input
left = 0, right = 0
Output
0

Example 3

Input
left = 1, right = 2147483647
Output
0

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

ANDing every number from 0 to 2^31 - 1 would TLE — you need a constant-time observation.

Hint 2

Any bit that flips somewhere in the range becomes 0 in the AND. The result equals the common binary prefix of left and right.

Hint 3

Right-shift both endpoints in lockstep until they're equal, counting the shifts. Then shift the equal value back left by that count.

Solution approach

Reveal approach

Find the common prefix. Initialize shift = 0. While left != right, right-shift both by one and increment shift. When the loop exits, left == right and that value is the shared high-order prefix. Return left << shift. The intuition: when right > left, some bit must flip somewhere in the range; the lowest position where left and right differ is where the AND starts producing zeros. Higher-order bits stay constant — they form the prefix. O(log(max(left, right))) — at most 32 iterations. O(1) space. A one-liner variant: while (left < right) right = right & (right - 1), then return right.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Bitwise AND of Numbers Range and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →