Bitwise AND of Numbers Range
Last Updated: March 20, 2026
Understanding the Problem
We need the bitwise AND of every integer from left to right, inclusive. AND is an operation where a bit in the result is 1 only if that bit is 1 in every single number in the range. Even one 0 at any bit position across the entire range kills that bit in the final result.
What makes this interesting is the structure of consecutive numbers in binary. Consider what happens when you count from 5 to 7:
The lower bits flip like crazy as you count up. The higher bits stay stable. The AND of this range keeps only the stable high bits, which is 100 = 4.
This leads to the key observation: the result of AND-ing a range [left, right] is the common binary prefix of left and right, with all remaining lower bits set to 0. If left and right share the same top k bits, those bits survive. Everything below flips at least once in the range, producing a 0.
Key Constraints:
0 <= left <= right <= 2^31 - 1→ Values fit in a 32-bit signed integer. We're dealing with at most 31 bits (since the values are non-negative).- The range can be enormous (up to ~2 billion numbers), so iterating through every number is not feasible. We need O(log n) or O(1) based on the number of bits.
Approach 1: Brute Force
Intuition
The most straightforward approach is exactly what the problem says: start with left, AND it with left + 1, then AND that result with left + 2, and so on until you reach right. This directly computes the answer by definition.
There's a nice optimization we can add: if at any point the running result becomes 0, we can stop early. Once every bit has been zeroed out, no further AND operations can bring any bit back to 1.
Algorithm
- Initialize
resulttoleft. - Iterate from
left + 1toright. - AND each number with
result. - If
resultbecomes 0, return 0 immediately (early termination). - Return
result.
Example Walkthrough
Code
- Time Complexity: O(right - left). In the worst case, we iterate through every number in the range. For inputs like
left = 1, right = 2^31 - 1, that's over 2 billion iterations, which will time out. - Space Complexity: O(1). We only use a single variable to track the running result.
The bottleneck is iterating through potentially billions of numbers. But most of that work is wasted, since we're AND-ing numbers just to zero out bits we could have predicted would become 0. Can we find the common prefix of left and right directly, without scanning the entire range?
Approach 2: Bit Shift (Common Prefix)
Intuition
Here's the key observation that makes this problem elegant. Consider the binary representations of left and right:
The leftmost bits where they agree (01) form the common prefix. Everything to the right of where they first disagree will get zeroed out by the AND, because the range contains numbers that flip those bits.
Why? If left and right differ at bit position k, then somewhere in the range [left, right], there's a number where bit k is 0 and another where bit k is 1. AND-ing a 0 with anything gives 0. And every bit below position k is even more volatile, so those all become 0 too.
So the algorithm is: keep right-shifting both left and right until they're equal. At that point, you've found their common prefix. Then left-shift back by the number of shifts to restore the prefix to its original position, with zeros filling in the lower bits.
When left and right differ at some bit position, the range between them must contain at least one number where that bit is 0 and one where it's 1. AND-ing those together zeros that bit. Every bit position below that is even more volatile (changes more frequently as you count), so those all become 0 too.
By shifting both numbers right until they match, we're stripping away all the differing lower bits. What remains is exactly the common prefix. Shifting back restores the prefix to its correct position, with zeros padding the lower bits.
Algorithm
- Initialize a shift counter to 0.
- While
leftis not equal toright, right-shift bothleftandrightby 1, and increment the shift counter. - Once they're equal, left-shift the common value by the shift counter.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(log n), where n is the maximum value of
right. We shift at most 31 times (for 32-bit integers). Each shift is O(1). - Space Complexity: O(1). Only a single counter variable for the number of shifts.
The bit shift approach is already O(log n) and O(1) space. But there's an alternative that avoids tracking a shift counter entirely. Instead of stripping bits from both sides, what if we only modified right by clearing its rightmost set bits until it becomes less than or equal to left?
Approach 3: Brian Kernighan's Algorithm
Intuition
Brian Kernighan's bit trick is one of those tools every bit manipulation fan should know: n & (n - 1) clears the lowest set bit of n. For example, 12 & 11 = 1100 & 1011 = 1000. It knocks off exactly one bit each time.
Here's how we can use it. Since right >= left, right has all the bits of the common prefix plus potentially some extra set bits in the lower positions. If we keep clearing the lowest set bit of right, we'll eventually land on a value that is less than or equal to left. At that point, right represents the common prefix (with lower bits already cleared), and that's our answer.
Why does this work?
Each time we clear a bit from right, we're effectively saying "this bit position cannot survive the AND, because right has it set but left doesn't (or the range spans a boundary that flips it)." We stop when right <= left, meaning all the remaining set bits in right are also set in left at the same positions, which is exactly the common prefix.
Algorithm
- While
rightis greater thanleft, clear the lowest set bit ofrightusingright = right & (right - 1). - When
right <= left, returnright & left.
Example Walkthrough
Code
- Time Complexity: O(log n), where n is the value of
right. In the worst case, we clear all set bits inright, which is at most 31 for a 32-bit integer. In practice, it's often fewer iterations than Approach 2. - Space Complexity: O(1). No extra data structures needed.