181. Bitwise AND of Numbers Range
You receive two integers left and right with left <= right. Take every integer in the inclusive range [left, right] and fold them all together with the bitwise AND operator; return the resulting integer.
For example, for left = 5, right = 7 the answer is 5 & 6 & 7 = 4.
The range can contain more than two billion numbers, so actually AND-ing them one by one is hopeless. Ask instead: which bit positions can possibly keep a 1 across the entire range?
Example 1:
Input: left = 5, right = 7
Output: 4
Explanation: In binary: 101 & 110 & 111 = 100, which is 4.
Example 2:
Input: left = 12, right = 15
Output: 12
Explanation: 1100 & 1101 & 1110 & 1111 = 1100. The two high bits are shared by the whole range; both low bits hit a 0 somewhere.
Example 3:
Input: left = 0, right = 1
Output: 0
Explanation: Any range that contains 0 must AND to 0.
Constraints:
- 0 ≤ left ≤ right ≤ 2³¹ - 1
Hints:
If a bit position flips anywhere inside the range, its AND is 0. Counting up from left to right, the low bits cycle constantly — only the high bits that left and right share can survive.
So the answer is the common binary prefix of left and right, padded with zeros. Shift both numbers right until they become equal, then shift the shared value back left the same number of steps.
Alternative: while right > left, do right &= right - 1 (clear the lowest set bit of right). It stops on a value <= left that keeps only bits common to the whole range.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: left = 5, right = 7
Expected output: 4