Bitwise AND of Numbers Range

1. Define the problem

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive. Any bit position where left and right disagree gets AND-ed to 0 by some number in between, so only their common binary prefix survives. Right-shift both numbers together until they match, counting the shifts, then shift that common prefix back into place.

Constraints

0 ≤ left ≤ right ≤ 2³¹ - 1

Example

Inputleft = 5, right = 7

Output4

Explanation 5 (101), 6 (110), 7 (111) AND together to 100 = 4.

2. Know the words first

In plain terms

Common binary prefix: The leading bits that left and right share before their binary representations first differ — every bit after that point is guaranteed to be cleared by some number crossed in the range.

3. Visualize the solution

Shift both bounds right together until they match

Statusinit

left=5 (101), right=7 (111). They differ, so shift both right. shift=1.

What happens in this step

left: 5 >> 1
  5 = 00000101
      --------
      00000010  =  2

right: 7 >> 1
  7 = 00000111
      --------
      00000011  =  3

Both numbers drop their lowest bit. left=2, right=3 still disagree, so shifting continues. shift becomes 1.

Step 1 of 4

Steps to visualize

While left is less than right, shift both left and right one bit to the right, and count the shift.
Stop once left equals right — that value is their shared binary prefix.
Shift that shared prefix back left by the number of shifts counted.
The result is the bitwise AND of every number in the original range.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Shift both bounds right together until they match

Statusinit

left=5 (101), right=7 (111). They differ, so shift both right. shift=1.

What happens in this step

left: 5 >> 1
  5 = 00000101
      --------
      00000010  =  2

right: 7 >> 1
  7 = 00000111
      --------
      00000011  =  3

Both numbers drop their lowest bit. left=2, right=3 still disagree, so shifting continues. shift becomes 1.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function rangeBitwiseAnd(left, right) {
  let shift = 0;

  while (left < right) {
    left >>= 1;
    right >>= 1;
    shift++;
  }

  return left << shift;
}

Time: O(log n), bounded by the bit width
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`left = 5, right = 7`	`4`	example from the docstring
`left = 0, right = 0`	`0`	smallest valid input, a single value range of just 0
`left = 1, right = 2147483647`	`0`	a very wide range collapses to no shared prefix
`left = 5, right = 5`	`5`	left equals right, no shifting needed
`left = 8, right = 9`	`8`	a two-number range that only differs in the lowest bit
`left = 26, right = 30`	`24`	a range sharing several high bits above the differing low bits

Bitwise AND of Numbers Range