Bitwise AND of Numbers Range

def rangeBitwiseAnd(left, right):
    shift = 0
    while left < right:     # they differ: drop a bit
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift    # prefix, then zeros

Bitwise AND of Numbers Range. You're given two numbers, left and right. AND together every whole number from left to right, and return the result.

Five to seven gives four: one oh one, one one oh, and one one one share only the top bit. Zero to zero gives zero. And one up to the largest thirty-two bit integer gives zero too.

The naive way ANDs the numbers one by one. But a range can hold over two billion numbers, so that loop could run two billion times.

Here's the trick. Think of each bit as a candle. AND keeps a candle lit only if it's lit in every number. Counting from left to right, any bit that flips even once goes out for good. The only bits that never flip are the leading bits that left and right share. So the answer is their common prefix, followed by zeros.

In code, shift both numbers right until they're equal, counting the shifts. What remains is the shared prefix. Shift it back left by that count, and the dropped bits return as zeros.

Try twenty-six to thirty. Light all five candles. Twenty-six blows out two, twenty-seven none, and twenty-eight a third. Twenty-nine and thirty change nothing, so two candles stay lit: twenty-four. The shifts agree: after three shifts, both are one one, which is three. Shift back three places: twenty-four.

Each shift drops one bit, so there are at most thirty-two: order log right time, and order one space.

Flipping bits go dark. Keep the common prefix, and pad with zeros. That's Bitwise AND of Numbers Range.