Bitwise AND of Numbers Range
Problem Description
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
Solve it on LeetCode
Approaches
1. Bitwise AND
Intuition:
The simplest method is to calculate the bitwise AND for every number in the range [m, n]. This approach guarantees that we consider every number but can result in unnecessary computations. The key observation in this approach is that any bit position that becomes zero remains zero for all subsequent numbers in the range.
Steps:
- Initialize a result variable with the value of
m. - Iterate through numbers from
m + 1ton. - Perform a bitwise AND operation between the result and the current number.
- Return the result.
This approach iterates over the range and progressively accumulates the AND result. However, this method can be quite inefficient for large ranges.
Code:
- Time Complexity: O(n - m), where n and m are the given range bounds. This can be very large if the range is big.
- Space Complexity: O(1) as we are using a constant amount of extra space.
2. Bit Manipulation - Common Prefix
Intuition:
In any range of numbers where the upper and lower bounds differ, certain trailing bits in the binary representation will vary. We can track how much both numbers need to be right-shifted until they match, effectively finding a common prefix. This prefix will form the result since any bits that remain the same between m and n should dominate the final AND operation.
Algorithm:
- Initialize a shift counter to 0.
- While m is not equal to n, right shift both m and n.
- Increment the shift counter each time you right shift.
- The result is the common prefix left-shifted back to its original position.
This approach efficiently finds the common range prefix, highlighting where numbers differ.
Code:
- Time Complexity: O(log n), where n is the upper bound of the range. We are finding the point of divergence in bits.
- Space Complexity: O(1) as we use a constant amount of extra space.