Bitwise AND of Numbers Range
The key idea
The bitwise AND of a whole range equals the common binary prefix of
left and right, with every lower bit set to 0. Any bit that differs between left and right must flip somewhere inside the range, so that bit becomes 0 in the AND.Problem
Given two integers left and right that represent the inclusive range [left, right], return the bitwise AND of all the numbers in this range.
That is, compute left & (left + 1) & ... & right. Because any bit position that changes anywhere inside the range gets ANDed against a 0 at some point, only the high-order bits that left and right share unchanged survive in the result.
Constraints
- 0 <= left <= right <= 2^31 - 1
Examples
Input: left = 5, right = 7
Output: 4
Input: left = 0, right = 0
Output: 0
Input: left = 1, right = 2147483647
Output: 0
Complexity
Time: O(log right) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Bit Manipulation problems
- Minimum Array EndMEDIUM
- Minimum Flips to Make a OR b Equal to cMEDIUM
- Missing NumberEASY
- Number of 1 BitsEASY
- Reverse BitsEASY
- Single NumberEASY
- Single Number IIMEDIUM
- Sum of All Subset XOR TotalsEASY
- Sum of Two IntegersMEDIUM