1158MediumBit Manipulation

Combining a Whole Range With AND

Tracked in this browser only

Trains the technique from

LeetCode 201Bitwise AND of Numbers Range

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Take every whole number from left to right, both ends included, and combine the lot with a bitwise AND.

Return the result.

Examples

Example 1

Input: left = 12, right = 15
Output: 12

All four numbers agree on their top bits and differ beneath, so only the agreed part survives.

Example 2

Input: left = 8, right = 16
Output: 0

The range crosses a power of two, so no bit place stays set right the way through.

Example 3

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

The range holds a single number, so that number is the result.

Constraints

0 <= left <= right <= 2147483647
left <= right

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def range_bitwise_and(left: int, right: int) -> int:

Java

public int rangeBitwiseAnd(int left, int right)

The intended approach

Time O(b) over the bit places.Space O(1).

A bit place survives the whole range only if it is set in every number of the range. Look at the highest place where `left` and `right` differ: somewhere inside the range that place must roll over, and rolling it over clears everything below it, so that place and every place under it end up cleared. Meanwhile every place above it agrees in `left` and `right` and cannot change anywhere between them, so those places survive exactly as they are. So the answer is the shared leading part of the two ends with zeros beneath. Finding it needs no loop over the range: shift both ends down one place at a time until they match, counting the shifts, then shift the matching value back up by that many places to put the zeros in.

Pythonentry point: range_bitwise_and

def range_bitwise_and(left, right):
    shift = 0
    while left < right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift

The obvious version

Walk every number of the range in turn, combining it into a running result with AND. Costs the whole width of the range, which is hopeless once the ends are billions apart.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_range_bitwise_and(left, right):
    total = left
    value = left
    while value < right:
        value += 1
        total &= value
    return total

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in