Bitwise AND of Numbers Range - Solution & Explanation
Problem Statement
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 - 1
Approach Overview
Problem 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 1: Bit-shift Reduction
This approach involves reducing the problem to finding a common ancestor in the binary tree representation of the numbers. When calculating the bitwise AND for numbers between left and right, we repeatedly right shift both numbers until they become equal, which means they share the same common prefix. The result will be left << the number of shifts.
C Explanation:This C solution keeps shifting both numbers to the right until they equal each other. The number of shifts is counted and the new shifted left value is returned shifted back to the left.
Complexity
Time Complexity: O(log N), where N is the range defined by right - left.
Space Complexity: O(1), no additional space required.
Approach 2: Prefix Matching
In this approach, we find the common prefix of the binary representations of the numbers in the range. This is achieved by continually shifting the left and right numbers until they become equal. The remaining value after shifting is the common prefix, which gives the result after reversing the shifts.
C Explanation: This approach applies bitwise operations to continuously zero out the lowest bit of right until left and right become equal.
Complexity
Time Complexity: O(log N), where N is the range between left and right, depending on how many bits need to be cleared.
Space Complexity: O(1).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Bit-shift Reduction | Time Complexity: O(log N), where N is the range defined by |
| Prefix Matching | Time Complexity: O(log N), where N is the range between left and right, depending on how many bits need to be cleared. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Bitwise AND of numbers range | Range AND query | Leetcode #201 • Techdose • 41,624 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Bitwise AND of Numbers Range easy or hard?
Bitwise AND of Numbers Range Python/Java solution
How to solve Bitwise AND of Numbers Range in O(n)?
What is the best approach for Bitwise AND of Numbers Range?
Is Bitwise AND of Numbers Range asked at Google/Amazon/Meta?
What data structure is used in Bitwise AND of Numbers Range?
What is the time complexity of Bitwise AND of Numbers Range?
Ready to solve this problem?
Practice Bitwise AND of Numbers Range with our built-in code editor and test cases.
Practice on FleetCode