The “Bitwise AND of Numbers Range” problem asks you to compute the bitwise AND of all integers within a given inclusive range, defined by two integers, a left bound and a right bound. The task is to apply the bitwise AND operation across every number in that range and return the final result.
At first glance, this problem may look like a simple loop that applies the AND operation repeatedly. However, when the range is large, that approach quickly becomes impractical. The real challenge is recognizing how bitwise operations behave across consecutive numbers and using that behavior to avoid unnecessary computation.
Why brute force iteration is not feasible
A straightforward solution would iterate from the left bound to the right bound and apply the AND operation step by step. While this is easy to understand, it performs poorly when the range is large. In many cases, the number of values in the range can be in the billions, making iteration completely unrealistic.
The problem is designed to push you away from brute force and toward reasoning directly about binary representations. The key to efficiency lies in understanding how bits change as numbers increase.
Observing how bits behave across a range
The critical observation is that as you move through consecutive integers, bits flip in predictable patterns. The least significant bit flips every number, the next bit flips every two numbers, the next every four, and so on.
When performing a bitwise AND across a range, any bit position that changes from zero to one or one to zero anywhere in the range will become zero in the final result. This is because the AND operation requires that bit to be one in every number in the range.
Why differing bits get eliminated
If the left and right bounds differ at a particular bit position, that bit must flip at least once somewhere within the range. Once a bit flips, there exists at least one number where that bit is zero, which forces the final AND result at that position to be zero.
This means that only the bits that remain identical across the entire range can survive in the final answer. All other bits are guaranteed to be zeroed out.
Focusing on the common binary prefix
From this observation comes the key insight: the result of the bitwise AND is simply the common binary prefix shared by the left and right bounds, with all remaining lower bits set to zero.
The common prefix represents the high-order bits that never change throughout the range. As soon as the left and right values differ at a certain bit, all bits at that position and below must be zero in the result.
Shifting to find the shared prefix
A clean way to extract the common prefix is to repeatedly shift both numbers to the right until they become equal. Each right shift removes one bit of detail from the numbers, effectively discarding lower bits where differences may occur.
Once the two values match, what remains is their shared prefix. Shifting this value back to the left by the same number of steps restores it to its original position, with zeros filling in the lower bits that cannot survive the AND operation.
Why this approach is correct
This method works because right-shifting both numbers preserves equality only for bits that are identical. The moment the two numbers differ at any position, that difference propagates through all lower bits in the range.
By stripping away differing lower bits and keeping only the shared higher bits, you are directly modeling what the AND operation does across the full range. The final result includes exactly the bits that never changed.
Time and space complexity considerations
The algorithm runs in constant time relative to input size because integers have a fixed number of bits. The number of shifts required is bounded by the word size of the integers, not by the numeric size of the range.
Space usage is constant, as the solution uses only a small number of variables and no additional data structures.
Why this problem is common in interviews
Bitwise AND of Numbers Range is a popular interview problem because it tests deep understanding of bitwise operations rather than surface-level syntax. Many candidates know how to use bitwise operators but struggle to reason about their behavior across ranges.
The problem also evaluates whether candidates can abandon brute force thinking and reason at the level of binary patterns and invariants.
What this problem teaches beyond bitwise AND
Beyond this specific operation, the problem teaches an important lesson about range-based computations. When an operation has strict requirements, like AND requiring every bit to be one, small changes across a range can have large effects on the result.
If you can clearly explain why only the common binary prefix survives, how shifting exposes that prefix, and why all lower bits must be zero, you demonstrate strong low-level reasoning skills. That depth of understanding makes “Bitwise AND of Numbers Range” an excellent exercise in binary thinking and efficient problem solving.
If you want more coding problems explained, check out:
Top comments (0)