# Bitwise AND of Numbers Range
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/bitwise-and-of-numbers-range)
Canonical: https://scaleengineer.com/dsa/problems/bitwise-and-of-numbers-range
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [Google](https://scaleengineer.com/companies/google)
---
## Problem
Given two integers `left` and `right` that represent the range `[left, right]`, return _the bitwise AND of all numbers in this range, inclusive_.

**Example 1:**

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

**Example 2:**

**Input:** left = 0, right = 0
**Output:** 0

**Example 3:**

**Input:** left = 1, right = 2147483647
**Output:** 0

**Constraints:**

* `0 <= left <= right <= 231 - 1`

# Approaches
## Brute Force Approach
The most straightforward approach is to perform a bitwise AND operation on all numbers in the range [left, right] one by one.
**Time:** O(right - left) in the worst case · **Space:** O(1)
**Pros:** Simple and easy to understand; Works well for small ranges
**Cons:** Very inefficient for large ranges; Will time out for inputs like [1, 2147483647]
### Explanation
In this approach, we iterate through all numbers from `left` to `right` and perform a bitwise AND operation on each number with the result of previous operations.

```java
public int rangeBitwiseAnd(int left, int right) {
    int result = left;
    for (int i = left + 1; i <= right; i++) {
        result &= i;
        // If result becomes 0, any further AND operations will remain 0
        if (result == 0) {
            break;
        }
    }
    return result;
}
```

This approach works correctly for small ranges, but it will time out for large ranges like [1, 2147483647] because we would need to perform billions of operations.
### Algorithm
1. Initialize `result` with the value of `left`
2. Iterate from `left + 1` to `right`:
   - Update `result = result & current_number`
   - If `result` becomes 0, break the loop (optimization)
3. Return `result`

## Bit Shifting Approach
A more efficient approach is based on the observation that the bitwise AND of a range of numbers is determined by the common prefix of the binary representation of the left and right boundaries.
**Time:** O(log(max(left, right))) - at most 32 iterations for 32-bit integers · **Space:** O(1)
**Pros:** Much more efficient than brute force; Works well for all input ranges, including very large ones; Avoids iterating through all numbers in the range
**Cons:** The logic might be less intuitive to understand at first
### Explanation
The key insight is that if we perform a bitwise AND of all numbers in a range [left, right], the result will have 1s only at bit positions where all numbers in the range have 1s.

If left and right have different bit lengths or differ at any bit position, all numbers between them will have at least one number with a 0 at that position, making the AND result 0 at that position.

The result is essentially the common prefix of the binary representations of left and right, followed by zeros.

```java
public int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    
    // Find the common prefix by right shifting both numbers
    while (left < right) {
        left >>= 1;
        right >>= 1;
        shift++;
    }
    
    // Shift back to get the final result
    return left << shift;
}
```

This approach efficiently finds the common prefix of the binary representations of left and right, which is the result of the bitwise AND of all numbers in the range.
### Algorithm
1. Initialize a counter `shift` to 0
2. While `left` is less than `right`:
   - Right shift both `left` and `right` by 1
   - Increment `shift` by 1
3. Return `left` left-shifted by `shift`

## Brian Kernighan's Algorithm
This approach uses Brian Kernighan's algorithm to find the common prefix of the binary representations of left and right more directly.
**Time:** O(log(max(left, right))) - at most 32 iterations for 32-bit integers · **Space:** O(1)
**Pros:** Very efficient for all input ranges; Often performs fewer operations than the bit shifting approach; Elegant solution using a well-known bit manipulation technique
**Cons:** Requires understanding of Brian Kernighan's bit manipulation technique; Slightly more complex to understand than the bit shifting approach
### Explanation
Brian Kernighan's algorithm is typically used to count set bits, but we can adapt it to solve this problem efficiently. The key insight is the same as the bit shifting approach - we need to find the common prefix of left and right.

Instead of shifting bits, we can directly remove the rightmost differing bit of right until it becomes less than or equal to left.

```java
public int rangeBitwiseAnd(int left, int right) {
    // If left is 0, the result will always be 0
    if (left == 0) {
        return 0;
    }
    
    // Keep removing the rightmost set bit of right until right <= left
    while (right > left) {
        // Remove the rightmost set bit
        right = right & (right - 1);
    }
    
    return right;
}
```

This approach efficiently finds the common prefix by removing the rightmost differing bits, which is equivalent to finding the bitwise AND of all numbers in the range.
### Algorithm
1. If `left` is 0, return 0 (optimization)
2. While `right` is greater than `left`:
   - Update `right = right & (right - 1)` (removes the rightmost set bit)
3. Return `right`

# Solutions
### CSharp

```csharp
public class Solution {
    public int RangeBitwiseAnd(int left, int right) {
        while (left < right) {
            right &= (right - 1);
        }
        return right;
    }
}
```

### Java

```java
class Solution {
public
  int rangeBitwiseAnd(int left, int right) {
    while (left < right) {
      right &= (right - 1);
    }
    return right;
  }
}

```

### JavaScript

```javascript
/** * @param {number} left * @param {number} right * @return {number} */ var rangeBitwiseAnd =
  function (left, right) {
    while (left < right) {
      right &= right - 1;
    }
    return right;
  };

```

### CPP

```cpp
class Solution {
public:
  int rangeBitwiseAnd(int left, int right) {
    while (left < right) {
      right &= (right - 1);
    }
    return right;
  }
};

```

### Python

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

```