Problem Statement

Bitwise AND of Numbers Range

You get two whole numbers, left and right. Think of every number from left up to right, all of them in a row. The job is to take the bitwise AND of that whole list and return the result. Bitwise AND means you line the numbers up in binary (the 1s and 0s a computer actually uses) and a spot in the answer is only a 1 if that spot is a 1 in every single number. If even one number has a 0 there, the answer has a 0 there. The big idea: as you walk across a range, the low bits (the ones on the right) flip back and forth, so AND wipes them out to 0. Only the part that stays the same in every number survives. That surviving part is the common starting bits, the prefix, that left and right share, with zeros filling the rest.

mediumBit ManipulationBit ManipulationTime: O(log n) · Space: O(1)

Signals to notice

AND of all numbers in rangecommon binary prefixdiffering bits become 0

Brute force first

AND all numbers — O(range). Very slow for large ranges.

The key insight

Shift both left and right until equal. That's the common prefix. Shift back. O(32) = O(1).

Trace it on `left = 5, right = 7`

start: left=5(101), right=7(111), shift=0 -> 5 != 7, keep shifting
iter1: left>>=1 -> 2(10), right>>=1 -> 3(11), shift=1 -> 2 != 3, continue
iter2: left>>=1 -> 1(1), right>>=1 -> 1(1), shift=2 -> 1 == 1, stop
loop ends: common prefix = left = 1, shift = 2
return left << shift = 1 << 2 = 4 (100)

What must stay true

Any bit where left and right differ = 0 in result. Common prefix = the AND result.

Shape of the loop

shift = 0
while left != right:
    left  = left  >> 1   # drop differing low bit
    right = right >> 1
    shift = shift + 1
return left << shift      # common prefix, padded with zeros

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Trying to AND all numbers — the bit-prefix approach is O(1).

Bit Manipulation Pattern