Bitwise AND of Numbers Range (LeetCode 201)

The problem

Given two integers left ≤ right (both between 0 and 2³¹ − 1), return the bitwise AND of every integer from left to right inclusive.

Input:  left = 5, right = 7
Output: 4

5 & 6 & 7 is 101 & 110 & 111 = 100, which is 4.

How to think about it

Start with brute force. Loop from left to right and AND everything together. That is O(right − left), which can be about two billion steps for the range [1, 2³¹ − 1]. Too slow.

The key insight: any bit below the common prefix gets cleared. Write left and right in binary and find where they first differ, reading from the top. Above that point they agree, and so does every number in between (they are sandwiched between left and right). At the first differing bit, left has a 0 and right has a 1, so somewhere in the range the count rolls over from ...0111... to ...1000.... Every lower bit is therefore 0 in at least one number, so the AND clears them all. The answer is the common binary prefix of left and right, followed by zeros.

Finding the prefix with shifts. Shift both numbers right one bit at a time until they are equal, counting the shifts. What remains is the shared prefix. Shift it back left by the same count to fill the cleared bits with zeros.

Which pattern is this? Bit manipulation, reasoning about prefixes of binary numbers. The tell is “AND (or OR) over a range of integers”, which you never compute one by one.

Approach

1. Set shift = 0.
2. While left < right, shift both right by one and add one to shift.
3. Now left == right is the common prefix. Return left << shift.

Solution

def range_bitwise_and(left, right):
    shift = 0
    while left < right:                        # they still differ somewhere
        left >>= 1; right >>= 1; shift += 1    # drop the lowest bit of both
    return left << shift                       # prefix followed by zeros
# range_bitwise_and(5, 7) -> 4

Dry run

On left = 5, right = 7:

They are equal, so the prefix is 1. Shifting it back by 2 gives 100, which is 4.

Complexity

• Time: O(log right), at most 31 iterations for 31-bit inputs.
• Space: O(1).

Edge cases and pitfalls

• left == right returns the number itself; the loop never runs (7, 7 gives 7).
• A range containing 0 returns 0.
• Very wide range (1, 2147483647): the numbers share no prefix, so the answer is 0 after 31 shifts.
• Looping over the range is the trap; it times out on large ranges.
• An alternative is while right > left: right &= right - 1, which clears right’s low set bits until it drops to left or below. Same idea, same complexity.

Related problems

• Number of 1 Bits (LeetCode 191): the n & (n - 1) trick used in the alternative.
• Counting Bits (LeetCode 338): another problem solved by looking at n >> 1.
• Reverse Bits (LeetCode 190): more shifting practice on fixed-width numbers.