Topics › Bit Manipulation › Interview Problems

XOR of numbers in a given range

Medium TUF ID 146 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given two integers L and R with 0 ≤ L ≤ R. Return the XOR of every integer in the inclusive range, that is L ^ (L + 1) ^ ... ^ R. The range can be enormous, so looping over it is not acceptable; the expected solution runs in constant time.

Constraints: 0 ≤ L ≤ R ≤ 2^31 - 1.

Example 1

L = 1, R = 4
answer = 4           // 1 ^ 2 ^ 3 ^ 4 = 3 ^ 3 ^ 4 = 0 ^ 4 = 4

Example 2

L = 5, R = 10
answer = 15          // 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10

Example 3

L = 3, R = 3
answer = 3           // a single number XORs to itself

Approach 1: Brute force

Intuition. Do what the statement says: start from 0, XOR in every integer from L to R. It is correct by definition and useful as a reference implementation for testing, but its running time grows with the length of the range, which can be two billion.

Algorithm.

1. Set xor = 0.
2. For i from L to R, set xor ^= i.
3. Return xor.

static int bruteForce(int l, int r) {
    int xor = 0;
    for (long i = l; i <= r; i++) xor ^= (int) i;    // long counter: i++ would overflow when r == Integer.MAX_VALUE
    return xor;
}

Complexity. Time O(R - L + 1). Space O(1).

The loop counter is a long on purpose. With an int counter and r == Integer.MAX_VALUE, the condition i <= r is always true, i++ wraps to a negative number and the loop never terminates.

Approach 2: Better, decide each bit by counting

Intuition. XOR works bit by bit and the bits do not interact. Bit b of the answer is 1 exactly when an odd number of integers in [L, R] have bit b set. So the question “what is the XOR of the range” becomes 31 independent questions “how many numbers in [L, R] have bit b set”, and each of those has a closed form.

Look at bit b as you count 0, 1, 2, ...: it is 0 for 2^b numbers, then 1 for 2^b numbers, then 0 again, with period 2^(b+1). So among 0 .. n there are (n + 1) / 2^(b+1) complete periods, each contributing 2^b ones, plus a partial period of length (n + 1) mod 2^(b+1) that contributes max(0, partial - 2^b) ones. A count over [L, R] is a count over [0, R] minus a count over [0, L - 1].

Algorithm.

1. For each bit b from 0 to 30:
2. Compute ones = countSetBit(R, b) - countSetBit(L - 1, b).
3. If ones is odd, set bit b in the result.
4. Return the result.

static int better(int l, int r) {
    int result = 0;
    for (int bit = 0; bit < 31; bit++) {
        long ones = countSetBit(r, bit) - countSetBit(l - 1, bit);
        if ((ones & 1) == 1) result |= 1 << bit;      // an odd number of 1s XORs to 1
    }
    return result;
}

static long countSetBit(int n, int bit) {
    if (n < 0) return 0;
    long period = 1L << (bit + 1);                    // the bit repeats: `half` zeros, then `half` ones
    long half = 1L << bit;
    long full = (n + 1L) / period * half;             // complete periods contribute `half` ones each
    long rem = (n + 1L) % period;                     // the unfinished period at the end
    return full + Math.max(0, rem - half);
}

Check it on n = 5 (000, 001, 010, 011, 100, 101): bit 0 has period 2, three full periods, no remainder, so 3 ones (1, 3, 5). Bit 1 has period 4, one full period giving 2 ones, remainder 2 which is not past the half, so 2 ones (2, 3). Bit 2 has period 8, no full period, remainder 6, 6 - 4 = 2 ones (4, 5). All correct.

Complexity. Time O(31) = O(1): a fixed number of bits, each in constant time. Space O(1).

This approach is the general-purpose tool: the same counting function answers “sum of set bits in a range”, “number of integers in a range with bit b set”, and similar queries. For XOR specifically there is an even shorter route.

Approach 3: Optimal, the period-4 pattern

Intuition. Write F(n) for 0 ^ 1 ^ ... ^ n. Then XOR(L..R) = F(R) ^ F(L - 1), because the terms 0 .. L - 1 appear in both and cancel. So we only need F.

Pair the numbers as (0, 1), (2, 3), (4, 5), .... The two members of a pair differ only in bit 0 (2k is even, 2k + 1 is 2k with bit 0 set), so each pair XORs to exactly 1. Therefore for odd n the value F(n) is the XOR of (n + 1) / 2 ones: 1 when that count is odd and 0 when it is even. For even n, F(n) = F(n - 1) ^ n. Spelling this out by n mod 4:

• n % 4 == 0: F(n - 1) = 0 (an even number of pairs), so F(n) = n.
• n % 4 == 1: (n + 1) / 2 pairs, an odd count, so F(n) = 1.
• n % 4 == 2: F(n - 1) = 1, and 1 ^ n = n + 1 because n is even and has bit 0 clear.
• n % 4 == 3: (n + 1) / 2 pairs, an even count, so F(n) = 0.

Algorithm.

1. Define xorUpTo(n) by the four cases above, returning 0 for n < 0.
2. Return xorUpTo(R) ^ xorUpTo(L - 1).

static int optimal(int l, int r) {
    return xorUpTo(r) ^ xorUpTo(l - 1);
}

static int xorUpTo(int n) {
    if (n < 0) return 0;
    return switch (n % 4) {
        case 0 -> n;
        case 1 -> 1;
        case 2 -> n + 1;
        default -> 0;
    };
}

Dry run of F(n) for n = 0 .. 7, checking the pattern against direct computation:

Now example 2, L = 5, R = 10: xorUpTo(10) has 10 % 4 == 2, so it is 11; xorUpTo(4) has 4 % 4 == 0, so it is 4; 11 ^ 4 = 1011 ^ 0100 = 1111 = 15. Matches the brute force.

Complexity. Time O(1): two constant-time evaluations. Space O(1).

The return 0 for negative n is what makes L = 0 work: xorUpTo(-1) is the XOR of an empty range, which is the identity 0.

Edge cases and pitfalls

• L = 0. L - 1 is -1; both xorUpTo and countSetBit return 0 for negative input, which is the correct XOR of nothing.
• L = R. Both formulas reduce to the single number: F(R) ^ F(R - 1) = R.
• R = Integer.MAX_VALUE. In xorUpTo, MAX_VALUE % 4 == 3, so the n + 1 branch (which would overflow) is never taken for it; the only n with n % 4 == 2 are at most MAX_VALUE - 1, and n + 1 fits. The brute force needs a long counter for the same input.
• Negative n % 4. Java’s % keeps the sign of the dividend, so (-1) % 4 == -1, which would fall into default. The explicit if (n < 0) return 0 guard runs before the switch, so the sign issue never arises.
• Thirty-one bits, not thirty-two. Inputs are non-negative, so bit 31 (the sign bit) is never set and better loops bit < 31. If the problem allowed negative ranges you would include bit 31 and rethink the counting function.
• Blind pattern memorisation. Interviewers often ask why the pattern holds; the pairing argument (2k ^ (2k + 1) = 1) is the two-sentence proof to have ready.

Related problems

• Single Number - I is the same cancellation property applied to an arbitrary array.
• Introduction to Bits and Tricks lists the XOR identities relied on here.
• Count the Number of Set Bits counts set bits over a range 1..n with the same period argument used in Approach 2.
• Count subarrays with given xor K uses XOR prefix values in exactly the way F(R) ^ F(L - 1) does.