Skip to main content
CodePeetCodePeet
CodePeet 250

Bitwise AND of Numbers Range

MEDIUMProblemSolveExternal Links

Description

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

The bitwise AND operation compares each bit position of two numbers: the result bit is 1 only if both input bits are 1, otherwise the result bit is 0. For a range of numbers, you compute:

left & (left + 1) & (left + 2) & ... & right

In other words, you AND every integer from left to right together and return the single resulting integer.

Examples

Example 1

Input: left = 5, right = 7

Output: 4

Explanation:

  • 5 in binary: 101
  • 6 in binary: 110
  • 7 in binary: 111

Performing AND: 101 & 110 & 111 = 100, which is 4 in decimal.

Notice that bit 2 (the leftmost 1) is 1 in all three numbers, so it survives the AND. Bits 0 and 1 vary across the range, so they become 0.

Example 2

Input: left = 0, right = 0

Output: 0

Explanation: The range contains only the number 0. The AND of a single number with itself is the number itself: 0.

Example 3

Input: left = 1, right = 2147483647

Output: 0

Explanation: The range spans from 1 all the way to 2^31 - 1. Somewhere in this range, every single bit position has a number where that bit is 0. For instance, the number 2 (binary 10) has bit 0 = 0, and 1 (binary 01) has bit 1 = 0. Eventually every bit gets cleared to 0, so the AND of this entire range is 0. This also shows why the brute force approach of iterating through all numbers is impractical — the range has over two billion numbers.

Constraints

  • 0 ≤ left ≤ right ≤ 2^31 - 1

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to do exactly what the problem says: iterate through every number from left to right and AND them all together.

Think of it like a voting system where every number gets a vote on each bit position. A bit in the final result is 1 only if every single number in the range has a 1 at that position. If even one number has a 0 there, the result bit becomes 0 — and once it's 0, it stays 0 no matter what future numbers say.

This immediately suggests a small optimization: if our running result ever becomes 0, we can stop early since AND-ing 0 with anything is still 0. But even with this shortcut, the worst case still requires us to visit every number in the range.

Step-by-Step Explanation

Let's trace through with left = 5, right = 7.

We represent each number in 4-bit binary for clarity.

Step 1: Initialize result = left = 5 (binary 0101). This is our starting accumulator.

Step 2: Next number is 6 (binary 0110). Compare with result (0101):

  • Bit 3: 0 & 0 = 0
  • Bit 2: 1 & 1 = 1
  • Bit 1: 0 & 1 = 0 (result already had 0 here)
  • Bit 0: 1 & 0 = 0 (6 has a 0 here, so this bit gets cleared!)
  • result = 0100 (4)

Step 3: Next number is 7 (binary 0111). Compare with result (0100):

  • Bit 3: 0 & 0 = 0
  • Bit 2: 1 & 1 = 1 (both have 1 — survives)
  • Bit 1: 0 & 1 = 0 (result already had 0)
  • Bit 0: 0 & 1 = 0 (result already had 0)
  • result = 0100 (4)

Step 4: We've reached the end of the range. Return result = 4.

Key observation: once bit 0 became 0 after AND-ing with 6, it stayed 0 forever. AND can only turn bits OFF, never ON.

Brute Force — AND Each Number in the Range — Watch how the running result loses bits as we AND it with each number in the range. Once a bit becomes 0, it can never become 1 again.

Algorithm

  1. Initialize result = left.
  2. For each number i from left + 1 to right:
    a. Compute result = result & i.
    b. If result becomes 0, return 0 immediately (early termination — AND-ing 0 with anything is 0).
  3. Return result.

Code

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int result = left;
        for (long long i = (long long)left + 1; i <= right; i++) {
            result &= (int)i;
            if (result == 0) return 0;
        }
        return result;
    }
};
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        result = left
        for i in range(left + 1, right + 1):
            result &= i
            if result == 0:
                return 0
        return result
class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int result = left;
        for (long i = (long) left + 1; i <= right; i++) {
            result &= (int) i;
            if (result == 0) return 0;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(right - left)

In the worst case, we iterate through every number in the range. When right - left is small, this is fast. But when the range is enormous (e.g., left = 1, right = 2^31 - 1 = 2,147,483,647), we'd need over two billion iterations — far too slow for any reasonable time limit.

The early termination helps when result becomes 0 quickly, but it doesn't improve the theoretical worst case.

Space Complexity: O(1)

We use only a single variable result regardless of the range size.

Why This Approach Is Not Efficient

The brute force iterates through every number in the range, making it O(right - left) in time. With constraints allowing right up to 2^31 - 1, the range can contain over two billion numbers. This causes Time Limit Exceeded on large inputs.

But here's the crucial observation that unlocks a better approach: we don't actually need to AND every number individually. Think about what happens to the bits as numbers increment from left to right:

  • The lowest bit (bit 0) flips between 0 and 1 on every consecutive number.
  • Bit 1 flips every 2 numbers.
  • Bit k flips every 2^k numbers.

So for any range that spans at least 2 numbers, bit 0 will see both a 0 and a 1 — meaning bit 0 will always be 0 in the AND result. For a range spanning at least 4 numbers, bits 0 and 1 are guaranteed to be 0. And so on.

The only bits that can survive the AND are the common prefix bits — the leading bits where left and right are identical. Every bit below the first point of disagreement between left and right will inevitably become 0 somewhere in the range. This insight lets us skip the iteration entirely and directly find the common prefix.

Better Approach - Common Prefix via Right Shifting

Intuition

Since the answer is the common binary prefix of left and right, we need a way to find that prefix efficiently.

Imagine writing left and right in binary and lining them up. Starting from the left (most significant bit), the bits are identical for some number of positions. At some point, the bits diverge — left has a 0 where right has a 1 (since left ≤ right). Every bit at and below this divergence point will become 0 in the AND of the full range.

To find the common prefix, we can repeatedly right-shift both left and right by 1 bit, discarding the least significant bit each time. We keep shifting until left and right become equal — at that point, we've stripped away all the bits where they differ, leaving only the common prefix.

Then we left-shift the result back by the same number of positions to restore the prefix to its correct place, with zeros filling the lower bit positions.

For example, with left = 5 (101) and right = 7 (111):

  • After 1 shift: left = 2 (10), right = 3 (11) — still different
  • After 2 shifts: left = 1 (1), right = 1 (1) — equal!
  • Shift back: 1 << 2 = 4 (100) — this is our answer

Step-by-Step Explanation

Let's trace through with left = 5, right = 7 using 4-bit binary.

Step 1: Initialize shift_count = 0. left = 5 (0101), right = 7 (0111).

Step 2: Are left and right equal? 5 ≠ 7, so no. The least significant bits differ. Right-shift both: left = 5 >> 1 = 2 (0010), right = 7 >> 1 = 3 (0011). shift_count = 1.

Step 3: Are left and right equal? 2 ≠ 3, still no. Right-shift again: left = 2 >> 1 = 1 (0001), right = 3 >> 1 = 1 (0001). shift_count = 2.

Step 4: Are left and right equal? 1 == 1, yes! We've found the common prefix. The value 1 represents the shared leading bits.

Step 5: Reconstruct the answer: left-shift the common prefix by shift_count. result = 1 << 2 = 4 (0100).

Step 6: Return 4. The two right-shifts stripped away bits 0 and 1 (which vary across the range), leaving only bit 2 (the common prefix).

Right-Shift — Finding the Common Binary Prefix — Watch how right-shifting both numbers strips away differing low-order bits until only the common prefix remains, then we shift back to reconstruct the answer.

Algorithm

  1. Initialize shift_count = 0.
  2. While left ≠ right:
    a. Right-shift both left and right by 1 bit.
    b. Increment shift_count.
  3. Return left << shift_count (the common prefix restored to its correct position).

Code

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left != right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
};
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shift = 0
        while left != right:
            left >>= 1
            right >>= 1
            shift += 1
        return left << shift
class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left != right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
}

Complexity Analysis

Time Complexity: O(log n) where n = right

Each iteration right-shifts both numbers by 1, halving them. The loop runs at most as many times as there are bits in the binary representation of right, which is log₂(right). For 32-bit integers, this means at most 31 iterations — an enormous improvement over the brute force's potentially billions of iterations.

Space Complexity: O(1)

We use only a single counter variable shift regardless of the input size.

Why This Approach Is Not Efficient

The right-shift approach is already very efficient at O(log n) time. However, it always performs exactly as many iterations as there are differing bit positions between left and right, regardless of the internal structure of the numbers.

For example, consider left = 9 (1001) and right = 12 (1100). The right-shift approach needs 3 iterations to converge:

  • Shift 1: left = 4 (100), right = 6 (110)
  • Shift 2: left = 2 (10), right = 3 (11)
  • Shift 3: left = 1 (1), right = 1 (1)

But there's a more elegant technique using Brian Kernighan's bit trick that can sometimes finish in fewer iterations. Instead of stripping one bit at a time from both sides, it directly clears the rightmost set bit of right in each step, potentially leaping over multiple zero-bits at once. For the same example (left = 9, right = 12), it finds the answer in just one iteration.

Optimal Approach - Brian Kernighan's Bit Clearing

Intuition

This approach exploits a beautiful property of binary arithmetic: the expression n & (n - 1) clears the rightmost set bit (the lowest-positioned 1) of any number n.

Why does this work? When you subtract 1 from a number, all the bits below the rightmost 1 flip: the rightmost 1 becomes 0, and all the 0s below it become 1. When you AND the original number with this modified version, the rightmost 1 cancels out and everything below it is zeroed.

For example: 12 = 1100. 12 - 1 = 11 = 1011. 12 & 11 = 1100 & 1011 = 1000 = 8. The rightmost set bit (bit 2) has been cleared.

The algorithm repeatedly applies this trick to right until right becomes less than or equal to left. At that point, right holds only the bits that are common to the entire range — exactly the AND result we need.

Why does reducing right this way work? Each time we clear right's lowest set bit, we're effectively saying: "this bit and everything below it will certainly be 0 in the AND of the range, because some number between left and right will have a 0 here." We keep clearing until right drops to or below left, at which point we've preserved only the stable common prefix bits.

Step-by-Step Explanation

Let's trace through with left = 5, right = 7 using 4-bit binary.

Step 1: Initialize. left = 5 (0101), right = 7 (0111).

Step 2: Check: is left (5) < right (7)? YES. Identify the rightmost set bit of right (0111) — it's bit 0.

Step 3: Compute right - 1 = 6 (0110). Subtracting 1 from 0111 flips just the lowest bit.

Step 4: Apply Brian Kernighan: right = 7 & 6 = 0111 & 0110 = 0110 = 6. The rightmost set bit (bit 0) has been cleared.

Step 5: Check: is left (5) < right (6)? YES. Rightmost set bit of right (0110) is now bit 1.

Step 6: Compute right - 1 = 5 (0101). Subtracting 1 from 0110 flips bit 1 to 0 and bit 0 to 1.

Step 7: Apply Brian Kernighan: right = 6 & 5 = 0110 & 0101 = 0100 = 4. Bit 1 has been cleared.

Step 8: Check: is left (5) < right (4)? NO (4 < 5). Loop terminates.

Step 9: Return right = 4 (0100).

Brian Kernighan — Clearing Rightmost Set Bits — Watch how the classic bit trick n & (n-1) clears the lowest set bit of right each iteration, rapidly converging to the common prefix with left.

Algorithm

  1. While left < right:
    a. Clear the rightmost set bit of right: right = right & (right - 1).
  2. Return right.

That's it — the entire algorithm is two lines. The elegance of Brian Kernighan's trick is that it directly erases the bits that would become 0 in the AND result, converging on the common prefix from above.

Code

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        while (left < right) {
            // Clear the rightmost set bit of right
            right &= (right - 1);
        }
        return right;
    }
};
class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            # Clear the rightmost set bit of right
            right &= right - 1
        return right
class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        while (left < right) {
            // Clear the rightmost set bit of right
            right &= (right - 1);
        }
        return right;
    }
}

Complexity Analysis

Time Complexity: O(log n) where n = right

Each iteration clears one set bit from right. A 32-bit integer has at most 31 set bits (since the problem guarantees non-negative values up to 2^31 - 1), so the loop runs at most 31 times. In practice, it often runs fewer iterations than the right-shift approach because it can skip over blocks of zeros.

For example, with left = 9 (1001) and right = 12 (1100): Brian Kernighan does 1 iteration (12 & 11 = 8, then 8 < 9 → stop), while right-shifting requires 3 iterations.

Space Complexity: O(1)

The algorithm modifies right in place and uses no additional data structures. Only a constant amount of memory is needed regardless of input size.