Bitwise AND of Numbers Range
Understanding the Problem
We need the bitwise AND of every integer from left to right, inclusive. A bit in the result is 1 only if that bit is 1 in every number in the range. A single 0 at any bit position anywhere in the range forces that bit to 0 in the result.
Consecutive numbers have a predictable binary structure. Counting from 5 to 7:
The low bits change on every increment, while the high bits stay fixed. The AND of this range keeps only the stable high bits: 100 = 4.
In general, the AND of a range [left, right] is the common binary prefix of left and right, with all lower bits set to 0. If left and right share the same top k bits, every number between them starts with that same prefix, so those bits survive. Every bit below the first disagreement flips at least once somewhere in the range, producing a 0.
Key Constraints:
0 <= left <= right <= 2^31 - 1→ Values fit in a 32-bit signed integer, and since they are non-negative, at most 31 bits are in play.rightcan equal2^31 - 1, the maximum signed 32-bit value, which matters for any loop that tries to increment past it.- The range can span up to about 2.1 billion numbers, so visiting every value is too slow. The solution has to work bit by bit, in O(log n) or better.
Approach 1: Brute Force
Intuition
Compute the answer by definition: start with left, AND it with left + 1, then AND that result with left + 2, and so on until you reach right.
One refinement cuts the cost in many cases: if the running result becomes 0, stop early. Once every bit has been zeroed, no further AND operation can bring any bit back to 1.
One implementation detail matters in languages with fixed-width integers. Because right can be the maximum 32-bit value, a loop counter that increments past right overflows. The loop below keeps the counter i strictly below right and ANDs in i + 1, so the counter never steps past the limit.
Algorithm
- Initialize
resulttoleft. - For each number from
left + 1throughright, AND it intoresult. - If
resultbecomes 0, return 0 immediately. - After the loop, 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 the scan itself: up to two billion AND operations to zero out bits whose fate is already determined by left and right. The next approach computes the common prefix of the two endpoints directly, without touching the numbers in between.
Approach 2: Bit Shift (Common Prefix)
Intuition
Compare the binary representations of left and right:
The leftmost bits where they agree (01) form the common prefix. Every bit at or below the first disagreement ends up 0 in the AND.
To see why, suppose left and right first differ at bit k. The bits above k match, and right > left, so left has a 0 at bit k and right has a 1. The range therefore contains the number written as the common prefix followed by 0111...1 (it is at least left) and its successor, the prefix followed by 1000...0 (it is at most right). AND-ing those two neighbors alone clears bit k and everything below it, so no bit below the prefix can survive.
The algorithm follows from this: right-shift both left and right together until they are equal. The shifts strip away the differing low bits, and the value that remains is the common prefix. Left-shift it back by the same count to restore the prefix to its original position, with zeros filling 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) time and O(1) space. Brian Kernighan's algorithm reaches the same prefix from the other direction: instead of shifting both numbers, it clears the low set bits of right until right no longer exceeds left, with no shift counter to track.
Approach 3: Brian Kernighan's Algorithm
Intuition
The identity n & (n - 1) clears the lowest set bit of n. For example, 12 & 11 = 1100 & 1011 = 1000. Each application removes exactly one set bit.
Since right >= left, right consists of the common prefix plus any extra set bits in lower positions. Repeatedly clearing the lowest set bit of right strips those extras one at a time, from the bottom up. The loop stops the first time right <= left, and at that moment right is exactly the common prefix followed by zeros, which is the answer. (If left equals right, the loop never runs and the answer is the number itself.)
The stopping condition is safe because of where the extra bits sit. Write right as the common prefix followed by its low bits; the highest of those low bits is bit k, the first position where left and right disagree (right has a 1 there, left has a 0). As long as bit k is still set, right > left, because bit k alone outweighs everything left has below it. Kernighan's step clears the low bits lowest-first, so bit k goes last, and the first value that satisfies right <= left is the bare prefix itself. No prefix bit is ever touched.
Algorithm
- While
rightis greater thanleft, clear the lowest set bit ofrightusingright = right & (right - 1). - When
right <= left,rightholds the common prefix. Returnright.
Example Walkthrough
Code
- Time Complexity: O(log n), where n is the value of
right. Each iteration clears one set bit, andrighthas at most 31. More precisely, the loop runs once per set bit ofrightat or below the first position whereleftandrightdisagree, which never exceeds the shift count of Approach 2. - Space Complexity: O(1). No extra data structures needed.