Bitwise AND of a Range

Compute the bitwise AND of all integers from a to b inclusive using a clever bit-level shortcut.

bitwise range optimization

Write a function `range_bitwise_and(a: int, b: int) -> int` that returns the bitwise AND of all integers from `a` to `b` inclusive. The inputs satisfy `0 <= a <= b <= 2^31 - 1`.

The naive approach of iterating over every number is too slow for large ranges. You must use a bit-wise strategy that reduces the problem efficiently.

**Requirements:**
- The function must compute the result without looping over each integer between `a` and `b`.
- The solution must work for the given constraints in O(1) or O(log(max(a,b))) time.

You will only need to implement the function. The grader will call your function with multiple test cases.

Constraints

0 <= a <= b <= 2^31 - 1. The function should run in O(log(max(a,b))) time or better.

Example

>>> range_bitwise_and(5, 7)
4
>>> range_bitwise_and(0, 0)
0
>>> range_bitwise_and(1, 2147483647)
0

20 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about the common prefix of the binary representations of a and b.

The result is the common high bits of a and b, with lower bits set to 0.

Repeatedly shift both numbers right until they are equal; then shift left by the same number of times.

Alternatively, clear the lowest set bit of b until it becomes <= a.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.