## Question:

It is necessary to calculate the XORs of all numbers on a given segment. The xor operation is familiar to me, but I don't know how to calculate the xors of all numbers. Tried to XOR first the first number with all the others, and these XORs XOR-il among themselves, also until the last number and then these XOR-il results, but this is wrong.

## Answer:

For obvious reasons, the `xor`

between an even number and the next odd number is `1`

. Therefore, and also because `xor`

is associative.

```
0 ^ 1 ^ 2 ^ 3 ^ ... ^ 2n-2 ^ 2n-1 =
(0 ^ 1) ^ (2 ^ 3) ^ ... ^ (2n-2 ^ 2n-1) =
1 ^ 1 ^ ... ^ 1 ^ 1 (n раз)
```

Those. if the sequence starts with an even number and ends with an odd number, then the result for it will be `1`

if the total number of terms is not divisible by `4`

, and `0`

if it is divisible.

That is, for example

```
40 ^ 41 ^ ... ^ 99999998 ^ 99999999 = 0
```

because `40`

is even, `99999999`

is odd and `99999999 - 40 + 1`

is divisible by 4

If the sequence starts with odd and/or ends with even, these numbers can be "doxed" to the result, because `xor`

is also commutative.

```
39 ^ 40 ^ 41 ^ ... ^ 99999998 ^ 99999999 ^ 100000000 =
(40 ^ 41 ^ ... ^ 99999998 ^ 99999999) ^ 39 ^ 100000000 =
0 ^ 39 ^ 100000000
```

Well, perhaps the fact that the `xor`

operation reverses itself will help

```
a ^ b ^ a = b
```

So

```
(0 ^ 1 ^ ... ^ n) ^ (0 ^ 1 ^ ... ^ m) = n+1 ^ n+2 ^ ... ^ m
```

where n ≤ m, but this is up to you