# c++ – I can not understand the simplest algorithm

## 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.

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

Scroll to Top