# LeetCode 201: Bitwise AND of Numbers Range

## Problem Restatement

We are given two integers `left` and `right`.

They define an inclusive range:

```python
[left, left + 1, left + 2, ..., right]
```

We need to return the bitwise AND of every number in that range.

The official statement says: given two integers `left` and `right` representing the range `[left, right]`, return the bitwise AND of all numbers in this range, inclusive. The constraints are `0 <= left <= right <= 2^31 - 1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `left` and `right` |
| Output | One integer: the AND of all numbers from `left` to `right` |
| Range | Inclusive |
| Constraint | `0 <= left <= right <= 2^31 - 1` |

Example function shape:

```python
def rangeBitwiseAnd(left: int, right: int) -> int:
    ...
```

## Examples

Example 1:

```python
left = 5
right = 7
```

The numbers are:

```python
5 = 101
6 = 110
7 = 111
```

Now compute:

```python
101
& 110
& 111
= 100
```

So the answer is:

```python
4
```

Example 2:

```python
left = 0
right = 0
```

There is only one number in the range, so the answer is:

```python
0
```

Example 3:

```python
left = 1
right = 2147483647
```

This range crosses many powers of two and contains enough variation that every bit position becomes `0` after AND.

So the answer is:

```python
0
```

## First Thought: Brute Force

The direct solution is to AND every number in the range.

```python
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        ans = left

        for x in range(left + 1, right + 1):
            ans &= x

        return ans
```

This is easy to understand.

For example:

```python
left = 5
right = 7
```

We compute:

```python
ans = 5
ans = ans & 6
ans = ans & 7
```

The final answer is `4`.

## Problem With Brute Force

The range can be very large.

For example:

```python
left = 1
right = 2147483647
```

A loop over every number would require more than two billion iterations.

So we need to use the structure of binary numbers instead of visiting every number.

## Key Insight

Bitwise AND keeps a bit as `1` only when every number in the range has that bit set to `1`.

If a bit changes from `0` to `1` or from `1` to `0` somewhere inside the range, then that bit becomes `0` in the final answer.

So the final answer is the common binary prefix of `left` and `right`.

For example:

```python
left  = 5 = 101
right = 7 = 111
```

The common prefix is:

```python
1__
```

The changing lower bits become `0`.

So the answer is:

```python
100 = 4
```

Another example:

```python
left  = 26 = 11010
right = 30 = 11110
```

The common prefix is:

```python
11___
```

The lower changing bits become `0`.

So the answer is:

```python
11000 = 24
```

## Algorithm

We can find the common prefix by shifting both numbers right until they become equal.

Each right shift removes one lower bit.

We count how many bits we removed.

When `left == right`, the remaining value is the common prefix.

Then we shift it back left by the number of removed bits.

Steps:

1. Set `shift = 0`.
2. While `left != right`:
   1. Shift `left` right by one bit.
   2. Shift `right` right by one bit.
   3. Increase `shift`.
3. Shift `left` back left by `shift`.
4. Return the result.

## Walkthrough

Use:

```python
left = 5
right = 7
```

Binary:

```python
left  = 101
right = 111
```

They are different, so shift both right.

```python
left  = 10
right = 11
shift = 1
```

Still different. Shift again.

```python
left  = 1
right = 1
shift = 2
```

Now they are equal.

The common prefix is:

```python
1
```

Shift it back left by `2`:

```python
1 << 2 = 100
```

So the answer is:

```python
4
```

## Correctness

The bitwise AND of a range keeps only the bit positions that are `1` in every number from `left` to `right`.

When `left` and `right` differ at some binary position, the range between them must vary across lower positions. Those lower positions cannot remain fixed as `1` for every number in the interval. Therefore, every bit after the first differing position becomes `0` in the final AND.

The only bits that can survive are the shared leading bits of `left` and `right`.

The algorithm repeatedly shifts both numbers right. This removes lower bits until only the shared leading prefix remains. When the two shifted values become equal, that value is exactly the common prefix.

The algorithm then shifts the prefix back to its original position. The removed lower bits are filled with zeros, which matches the behavior of AND over the full range.

Therefore, the algorithm returns the correct bitwise AND of all numbers in `[left, right]`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log right)` | Each loop removes one binary bit |
| Space | `O(1)` | Only a few integer variables are used |

Since `right <= 2^31 - 1`, the loop runs at most 31 times.

## Implementation

```python
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shift = 0

        while left != right:
            left >>= 1
            right >>= 1
            shift += 1

        return left << shift
```

## Code Explanation

We start with:

```python
shift = 0
```

This counts how many lower bits we remove.

The loop continues while the two numbers have different remaining prefixes:

```python
while left != right:
```

Inside the loop, we remove one low bit from both numbers:

```python
left >>= 1
right >>= 1
```

Then we record that one more bit was removed:

```python
shift += 1
```

When the loop ends, `left` and `right` are equal. That value is the common prefix.

Finally:

```python
return left << shift
```

This restores the prefix to its original bit position and fills the removed lower bits with zeros.

## Alternative Implementation

There is another common solution using this identity:

```python
right &= right - 1
```

This removes the lowest set bit of `right`.

We keep doing this while `right > left`.

```python
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right &= right - 1

        return right
```

This works because every removed bit is in a lower changing region that cannot survive the range AND.

The shifting version is often easier to explain. The `right &= right - 1` version is shorter.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.rangeBitwiseAnd(5, 7) == 4
    assert s.rangeBitwiseAnd(0, 0) == 0
    assert s.rangeBitwiseAnd(1, 2147483647) == 0
    assert s.rangeBitwiseAnd(8, 8) == 8
    assert s.rangeBitwiseAnd(26, 30) == 24
    assert s.rangeBitwiseAnd(10, 12) == 8

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `(5, 7)` | Standard example with changing low bits |
| `(0, 0)` | Single zero |
| `(1, 2147483647)` | Very large range |
| `(8, 8)` | Single number range |
| `(26, 30)` | Preserves a longer common prefix |
| `(10, 12)` | Checks a small nontrivial range |