Coding Interview PatternsBitwise AND of Numbers Range
MediumBitwise Manipulation
Bitwise AND of Numbers Range
Explanation & Solution
Description
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
Input: left = 5, right = 7
Output: 4
Explanation: AND of 5 (101), 6 (110), 7 (111) = 100 = 4
Constraints
0 <= left <= right <= 2^31 - 1
Approach
Bitwise Manipulation pattern
Key Insight
- As numbers increase from
lefttoright, lower bits cycle through all combinations, making their AND = 0. Only the common high-order bits survive. - Time: O(log n) | Space: O(1)