Abstract / Summary

Find the common prefix bits of two numbers and return it as the result of bitwise AND across a range.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 49% (1+ million submissions).

Typical patterns to solve this problem:

• Bit Manipulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the bitwise AND of all integers in the inclusive range [left, right]. It does so by progressively eliminating bits that cannot remain set across the entire interval, ultimately returning the common prefix of the binary representations of the two bounds.

Key Steps

Determining the Upper Bound Mask

mask = 1
while mask < max(left, right):
    mask <<= 1

The algorithm begins with a mask set to the least-significant bit. It then left-shifts the mask until it is at least as large as the larger of the two input values. At this point the mask represents the smallest power of two that exceeds or equals the maximum bound, effectively positioning a single 1 just beyond the most significant bit of the larger number.

Aligning the Masks of the Two Ends

while (left & mask) == (right & mask) and mask > 0:
    mask >>= 1

With the mask positioned above the highest set bit, the loop checks whether the bits of left and right under the current mask are identical. If they match, the mask is shifted right, moving the focus one bit lower. This continues until a bit position is found where the two numbers differ, or the mask becomes zero. The loop therefore isolates the highest differing bit, leaving the mask aligned with the first bit that can vary within the range.

Clearing Variable Bits

while mask > 0:
    left &= ~mask
    mask >>= 1

Starting from the mask that marks the first differing bit, the algorithm clears that bit and all less significant bits in left. It does this by AND-ing left with the complement of the mask, which forces the current bit to zero while leaving higher bits untouched. The mask is then shifted right to address the next lower bit, repeating until all bits that could change across the interval have been cleared. The resulting value of left is the common high-order prefix shared by every number in the range, which is precisely the desired bitwise AND.

Returning the Result

return left

After the clearing phase, left holds the final result, and the function returns it directly.

Edge Cases Handled

When left and right are equal, the first while loop positions the mask above the most significant bit, but the second loop immediately exits because the bits under the mask are identical and the mask is shifted down to zero. The subsequent clearing loop does not execute, leaving left unchanged, which correctly returns the original value.

If the range spans the entire width of an integer type (for example, left = 0 and right is the maximum 32-bit unsigned integer), the mask will be shifted down until it reaches zero in the alignment loop, because every bit position will differ between the two bounds. Consequently, the clearing loop will also run until the mask is zero, clearing all bits of left and yielding 0, which matches the expected result for a full-range AND.

When right is a power of two and left is just below it, the mask will stop at the bit representing that power of two. The clearing loop will then zero out that bit and all lower bits, producing the correct result of 0 because the range includes numbers with both the high bit set and cleared.

Performance Optimizations

The algorithm avoids iterating over every integer in the interval, which would be prohibitive for large ranges. Instead, it works directly with the binary representation, using bitwise shifts and masks that execute in constant time per iteration. The first loop runs at most the number of bits required to represent the larger bound, establishing a starting point for the subsequent steps. The second loop reduces the mask until the first differing bit is found, guaranteeing that only the necessary bits are examined. The final clearing loop processes each remaining bit exactly once, ensuring that the total number of iterations is bounded by the word size of the integer type (typically 32 or 64). This approach yields a highly efficient solution that scales with the size of the integer representation rather than the magnitude of the numeric range.

Imagine you have two big boxes filled with secret code numbers called bits, which are just tiny switches that are turned either on or off. You want to see which switches stay exactly the same when you look at every number between a starting point and an ending point.

The first part of this work is like making a giant flashlight that is big enough to shine over the largest number you have. It keeps doubling in size until it is wide enough to cover everything.

Next, you move the flashlight from the left side to the right side to check if the switches match. If a switch is on in one place but off in another, it means that switch is wobbly and cannot be trusted, so you keep moving until you find the ones that are perfectly steady and never change.

Finally, you go through all the remaining switches that were wobbly and you turn them all off. Once that is done, the only switches that are left turned on are the ones that stayed steady the entire time. This gives you a final set of switches that represents the pattern shared by all the numbers in your range.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: logarithmic
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python				Java				TS
	WalkCCC	C++	Python				Java
	leetcode.ca	C++	Python			JS	Java	C#		Go
	LeetcodeHelp	C++	Python				Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python				Java
github	aylei				Rust
	begeekmyfriend			C
	BigEggStudy							C#
	black-shadows	C++
	charles-wangkai						Java
	chenyanzhe	C++
	DimitrisJim			C
	everthis					JS
	fpdjsns	C++
	fsq	C++
	gaosq0604		Python
	halfrost									Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx			C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	pruthvikp		Python
	qiyuangong	C++
	ruoru				Rust
	suxrobGM							C#
	varunu28						Java
	XiaotaoGuo	C++
	yuanliu666								Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fpdjsns	C++
fsq	C++
gaosq0604	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
pruthvikp	Python
qiyuangong	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
XiaotaoGuo	C++
yuanliu666	Kotlin

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality