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