← DSA Atlas
Dedicated problem page · #201

Bitwise AND of Numbers Range

MediumBit ManipulationCommon bit prefixBit shifting
Solve on LeetCode ↗
201
MediumBit ManipulationBit shiftingCommon bit prefix

Bitwise AND of Numbers Range

Given two integers left and right that represent an inclusive range [left, right], return the bitwise AND of every integer in that range.

Open official problem prompt ↗
In plain English

Compute the AND of a potentially enormous run of consecutive integers without touching each one.

Picture it like this

Think of two odometer readings. Whatever leading digits are identical stay fixed; every digit that changed at least once between the two readings must have rolled through all its values, so it cannot be pinned to a single value — for AND, those unstable positions collapse to 0.

Example
Input
left = 5, right = 7
Output
4
Why
5 & 6 & 7 = 101 & 110 & 111 = 100 = 4
Constraints
0 <= left <= right <= 2^31 - 1
Pattern lesson

See the pattern, then code

Common bit prefix
Recognition clue

You are asked for the AND across a whole contiguous range, and the range can be huge (up to 2^31), so iterating every number is impossible — that signals looking for the shared high-bit prefix.

↗
Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. A bit is 1 in the answer only if it stays 1 across the entire range. Any bit position that flips at least once within [left, right] becomes 0 after the AND, and the low bits always flip somewhere in a range of length > 1. So the answer is exactly the common binary prefix of left and right, padded with zeros.

New words, made simpleKnow these before the algorithm
Bitwise AND
A bit is 1 only if it is 1 in every operand.
Common prefix
The leading run of bits that left and right share identically.
Right shift (>>)
Drop the lowest bit, dividing by two and revealing the next-higher bit.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force loop

The range can hold billions of numbers, so this times out immediately.

Start from left and AND every integer up to right.

Time O(n)Space O(1)
Best choiceShift to common prefix

Runs in at most ~31 steps regardless of range size.

Right-shift both endpoints until they match, then shift the match back to reinsert trailing zeros.

Time O(log n)Space O(1)
The rule we keep true

Invariant

After k shifts, left and right hold their top (bitwidth - k) bits; the algorithm stops the moment those truncated values agree, which is exactly the shared prefix.

Why this is correct

Reasoning

If left != right, the least significant differing bit and everything below it takes on both 0 and 1 somewhere in the range, so each such bit ANDs to 0. Discarding those bits by shifting until the endpoints match isolates the untouched high prefix, and every discarded low bit is correctly 0.

The algorithm in three movesSay these aloud before coding
1Shift both left and right right by one until they become equal, counting the shifts

5=101, 7=111, differ -> shift, count=1

2Once equal, that value is the shared prefix

2=10, 3=11, differ -> shift, count=2

3Shift the shared prefix back left by the number of shifts to restore the trailing zeros

1=1 == 1=1, stop; 1 << 2 = 100 = 4

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
1010
1101
1112
1 · Readleft=5 (101), right=7 (111)
2 · AskAre the endpoints equal yet?
3 · Update stateshift=0
4 · ResultNot equal, shift both right
Key takeaway

The three range values share the high bit; the lower two bits flip, so only 100 survives the AND.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Collapse to the shared prefix

    Shifting both endpoints right by one each iteration removes the lowest, potentially unstable, bit and counts how many bits were dropped.

  2. 2
    Lines 7Reinsert trailing zeros

    Every dropped bit ANDs to 0, so shifting the matched prefix back left restores those positions as zeros.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • left == right returns left unchanged (loop never runs)
  • left = 0 forces the answer to 0 since 0 is in the range
  • A range that spans a power of two, like [1, 3], collapses to 0
!

Common beginner mistakes

  • Trying to loop over the range and timing out
  • Forgetting to shift the prefix back, which drops the trailing zeros
  • Assuming the answer equals left & right — that is only true when no intermediate bit flips, which is not guaranteed
Check your understanding

Why is the AND over [4, 7] equal to 4 but the AND over [4, 8] equal to 0?

More in Bit Manipulation

#50Pow(x, n)Fast exponentiation (binary exponentiation)#89Gray CodeBinary-to-Gray transform (i XOR i>>1)#136Single NumberXOR cancellation#137Single Number IIBitwise finite-state counting (mod-3 per bit)#190Reverse BitsBit-by-bit reversal accumulation#191Number of 1 BitsBrian Kernighan bit clearing