Watch 10 video solutions for Bitwise AND of Numbers Range, a medium level problem involving Bit Manipulation. This walkthrough by Techdose has 39,894 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: left = 5, right = 7 Output: 4
Example 2:
Input: left = 0, right = 0 Output: 0
Example 3:
Input: left = 1, right = 2147483647 Output: 0
Constraints:
0 <= left <= right <= 231 - 1Problem Overview: Given two integers left and right, compute the bitwise AND of every number in the inclusive range [left, right]. A naive approach would AND each number sequentially, but large ranges make that too slow. The key observation: if any bit position changes within the range, that bit becomes 0 in the final result.
Approach 1: Bit-shift Reduction (O(log n) time, O(1) space)
This approach repeatedly right-shifts both left and right until they become equal. Every shift removes the least significant bit where differences may occur. Each time the values differ, the lower bits must eventually flip within the range, meaning they contribute 0 to the final AND result. Count how many shifts are performed, then left-shift the common value back by that amount to restore the shared prefix.
The insight: the final answer is simply the common binary prefix of left and right. All trailing bits become zero because the range includes numbers where those bits toggle. Since integers have at most 32 bits, the loop runs at most 32 iterations, making the runtime effectively constant. This method relies heavily on bit manipulation operations like >> and <<.
Approach 2: Prefix Matching (O(log n) time, O(1) space)
This method focuses directly on identifying the longest common binary prefix between left and right. Start from the most significant bit and compare positions while both numbers share the same value. Once a mismatch occurs, all remaining bits must be zero in the result because the range includes numbers with both 0 and 1 in those positions.
You can implement this by repeatedly clearing the lowest set bit of right using right = right & (right - 1) until right <= left, or by comparing prefixes through shifts. Both techniques rely on properties of bitwise operators and binary representation. The algorithm runs in at most the number of bits in the integer (around 32 for typical constraints), keeping time complexity logarithmic.
Recommended for interviews: Interviewers typically expect the bit-shift reduction approach. It demonstrates clear understanding of how ranges affect binary bits and avoids unnecessary iteration through the range. A brute-force AND across all numbers shows the basic idea but fails performance constraints for large ranges. Recognizing that the result equals the shared binary prefix shows strong understanding of bit manipulation patterns frequently tested in technical interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit-shift Reduction | O(log n) | O(1) | Best general solution. Quickly finds the common binary prefix by shifting both numbers. |
| Prefix Matching / Bit Clearing | O(log n) | O(1) | Useful when leveraging bit tricks like clearing the lowest set bit of the upper bound. |