1261. The XOR of Every Number From l to r

For each of q queries l r, print the bitwise XOR of every INTEGER from l to r inclusive. These are the numbers themselves, not entries of an array.

1 3 -> 0 1 ^ 2 ^ 3 5 5 -> 5 4 6 -> 7 4 ^ 5 ^ 6 0 7 -> 0

## What most people try first

The loop from l to r. It is correct and the range can hold 10^18 numbers, so it is not slightly slow, it cannot finish. Problem 731 does not help either: that one is given an array and may build a prefix table over it, and here no array exists to tabulate. There are 10^18 positions and q is 10^5.

## Reduce to a prefix, then find the prefix's pattern

Define f(n) = 0 ^ 1 ^ ... ^ n. Then, exactly as in #731,

XOR(l..r) = f(r) ^ f(l - 1)

and when l is 0 the second term is f(-1), which is the XOR of nothing, so 0.

That leaves f(n), and f has a short closed form. Look at four consecutive numbers starting at a multiple of 4, say 4k, 4k+1, 4k+2, 4k+3. Above bit 1 all four agree, so each of those higher bits appears four times and cancels in pairs. The bottom two bits run 00, 01, 10, 11, and each of bit 0 and bit 1 appears exactly twice among them, so they cancel too. Every block of four starting at a multiple of four therefore XORs to 0.

So f(n) depends only on n mod 4 and the leftover tail:

n mod 4 == 0 -> n n mod 4 == 1 -> 1 n mod 4 == 2 -> n + 1 n mod 4 == 3 -> 0

Read it off the blocks: at n = 4k+3 the last block is complete and everything cancels, giving 0. At n = 4k only 4k is left over, so f = n. At n = 4k+1 the leftover is 4k ^ (4k+1), which is 1 because they differ only in bit 0. At n = 4k+2 it is 1 ^ (4k+2) = n + 1, since 4k+2 is even and setting its bit 0 adds one.

## Cost

O(1) per query, so O(q) overall, against a loop that cannot run at all.

## Width

Values reach 10^18, below 2^60, so n + 1 and every intermediate fit in a signed 64-bit integer, whose limit is 9223372036854775807. A signed 32-bit integer cannot hold the inputs: truncating 10^18 to 32 bits gives -1486618624, and a build that does so answers 0 on the largest declared tests where the correct answers are 1000000000000000000 and 524287. That was run rather than assumed.

In JavaScript the hazard is the same one as everywhere else in this block: ^ coerces to signed 32 bits, so f(r) ^ f(l-1) on Numbers discards everything above bit 31. The reference uses BigInt, and takes n % 4n on the BigInt rather than converting down first.

Constraints - `1 ≤ q ≤ 100000` - `0 ≤ l ≤ r ≤ 1000000000000000000`