201. Bitwise AND of Numbers Range
Model: qwen3.5:9b
Topics: Bit Manipulation
FAANG asked: 0
Acceptance rate: 39.7%
Problem Breakdown
We are given two integers, left and right, defining a contiguous range [left, right]. Our goal is to compute the bitwise AND of every integer within this inclusive range.
Inputs: Two non-negative integers left and right where .
Output: A single integer representing the result of applying the bitwise AND operator across all numbers in the sequence from left through right.
Constraints & Edge Cases:
- The range can be very large (up to 32-bit integers), so iterating through every number is not feasible.
- If
left == right, the result should simply be that single number itself. - Since Python handles arbitrary-precision integers, we don’t need to worry about overflow wrapping like in C/C++, but our logic must respect the 32-bit constraint contextually (i.e., treating them as binary representations).
Intuition
Let’s start with a brute-force approach: iterate from left up to right, performing an AND operation on each number.
- Time Complexity: , where . If the range is large (e.g., 0 to ), this will time out because we cannot perform billions of operations in a standard interview window.
- Space Complexity: .
Key Insight:
Consider the binary representation of left and right. If two numbers differ at any bit position, say from most significant to least significant, that difference implies there is no guarantee for that specific bit column across all intermediate values. Specifically:
- Any bit where
leftandrightshare a common prefix (from the MSB downwards) will remain unchanged throughout the entire range because we are moving contiguously between them without crossing over to flip those higher-order bits back or forth in a way that introduces zeros into the AND result. - Once we encounter the first bit position where they differ, all subsequent lower bits can be anything (0s and 1s). However, for any column below this divergence point, there will exist at least one number in the range with a
0at that specific column due to how binary counting works. Since AND requires all numbers to have a1, if even one has a0, the result is0. - Therefore, the final answer consists only of the common prefix bits shared by both
leftandright. All differing lower bits effectively become 0 in the result.
Approach
To isolate this common prefix efficiently:
- Initialize a counter to track how many times we shift right (to know where to restore).
- While
leftis not equal toright, perform a bitwise right shift (>>= 1) on both numbers simultaneously and increment the counter. This strips away all bits that differ or are irrelevant, leaving only the matching prefix inleft. - Once they match (meaning we’ve stripped down to just the common MSB part), restore the value by shifting left (
<<=) using the stored count of shifts.
This approach effectively finds the longest binary string shared at the start of both numbers’ representations, which is exactly what remains after ANDing a contiguous range.
Complexity Analysis
- Time Complexity: where is the number of bits (up to 32 for standard integers). We shift right until
leftandrightmatch, which takes at most 31 iterations. This is extremely fast compared to linear iteration over values; effectively constant time () given fixed-width integer constraints. - Space Complexity: . We only use a few integer variables (
shift, modified copies of inputs).
Solution
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shift = 0
# Shift both numbers to the right until they are equal.
# This effectively strips away all bits that differ between them.
while left != right:
left >>= 1
right >>= 1
shift += 1
# Restore the common prefix by shifting back to the original magnitude.
return left << shift
Edge Cases Handled
left == right: Thewhileloop condition is false immediately,shiftremains 0, and we returnleft, which is correct (AND of a single number).- Range resulting in 0: If the numbers differ significantly at high bits (e.g., Example 3), shifting continues until both become 0. The result correctly returns 0.
right - left == 1: They share a common prefix except for one bit; logic strips that differing suffix and preserves the MSB match, returning correct AND value (e.g.,8 & 9 = 8).