159. Bitwise AND of Numbers Range

ANDing an entire range zeroes out every bit that ever flips within it. The only bits that survive are the leading bits that are identical in left and right — their common binary prefix. Shift both right until they're equal, then shift the shared value back.

Idea

Any bit position that changes anywhere in [left, right] becomes 0 in the AND (some number has a 0 there). Low bits cycle rapidly, so they always flip across a range; only the high bits that are the same in left and right — the common binary prefix — remain 1.

So the answer is that common prefix followed by zeros. We find it by shifting both numbers right until they're equal (counting the shifts), then shifting the shared value back.

Algorithm

1. shift = 0.
2. While left < right: left >>= 1, right >>= 1, shift += 1.
3. Return left << shift.

Worked example: left = 5 (101), right = 7 (111)

• 5≠7 → shift → 2 (10), 3 (11), shift=1.
• 2≠3 → shift → 1, 1, shift=2.
• Equal at 1. Return 1 << 2 = 4 (100).

Indeed 5 & 6 & 7 = 4.

Complexity

• Time: O(log(max)) — at most 32 shifts.
• Space: O(1).

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