Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Bitwise AND of Numbers Range

Bitwise AND of Numbers Range

Master this topic with zero to advance depth.

Bitwise AND of Numbers Range

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Medium

Examples

Input: left = 5, right = 7
Output: 4
Input: left = 0, right = 0
Output: 0
Approach 1

Level I: Brute Force (Linear AND)

Intuition

Iterate from left to right and perform bitwise AND on all numbers. This is slow if the range is large.

Thought Process

  1. Initialize res = left.
  2. Iterate i from left + 1 to right.
  3. res &= i.
  4. Return res.

Pattern: Simulation

⏱ O(N) - Where $N$ is the number of integers in the range.💾 O(1) - Constant space.
java
public class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int res = left;
        for (long i = (long)left + 1; i <= right; i++) {
            res &= i;
            if (res == 0) break;
        }
        return res;
    }
}
Approach 2

Level II: Iterative Shift (Pre-calculation)

Intuition

Shift both left and right rightward until they are identical. The bits that are removed are the ones that fluctuate within the range. Finally, shift the common prefix back to its original position.

⏱ $O(1)$ - Maximum of 32 shifts.💾 $O(1)$
java
class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shifts = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shifts++;
        }
        return left << shifts;
    }
}
Approach 3

Level III: Optimal (Common Prefix / Brian Kernighan)

Intuition

The bitwise AND of a range is the common prefix of the binary representations of the range's endpoints. Any bit that changes within the range will eventually become 0 in the final AND result.

Thought Process

  1. While right > left:
    • right = right & (right - 1) (clears the rightmost set bit).
  2. Alternatively, shift both numbers right until they are equal, then shift back.

Pattern: Bitwise Prefix Match

⏱ O(1) - Max 32 iterations.💾 O(1) - Constant space.

Detailed Dry Run

left=5(101), right=7(111) Iteration 1: right = 7 & 6 = 6 (110). 6 > 5. Iteration 2: right = 6 & 5 = 4 (100). 4 < 5. Stop. Result: 4

java
public class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        while (right > left) {
            right &= (right - 1);
        }
        return right;
    }
}
← Previous QuestionSingle Number III
Next Question →Number of 1 Bits