Course4all

Bitwise AND of Numbers Range

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Bit Manipulation.

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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSingle Number III
Next Question →Number of 1 Bits