Bit Manipulation - Bitwise AND of Numbers Range

Given two integers left and right that represent a range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Input: left = 5, right = 7
Output: 4
Explanation: 5 (101) AND 6 (110) AND 7 (111) = 100 = 4.

Input: left = 1, right = 2147483647
Output: 0
Explanation: The AND of the full range results in 0.

The result is the common prefix of the binary representations of left and right. Any bit that differs between left and right will be 0 in the AND result. Shift both numbers right until they are equal — the remaining value is the common prefix, then shift it back left.

Count how many times we shift both left and right until they are equal.
The bits that differ between left and right become 0 in the AND result.
Shift the common prefix left by the number of shifts performed to restore position.

class Solution { public int rangeBitwiseAnd(int left, int right) { int shift = 0; while (left != right) { left >>= 1; right >>= 1; shift++; } return left << shift; } }

Complexity Analysis:

Time complexity: O(log n) — at most 32 shifts for 32-bit integers.
Space complexity: O(1) — constant extra space.