# How can xor keep many numbers?

• I can see how the xor solution works for an array like [1,2,1,3,2,4,3,...], where at most 2 numbers are combined with xor before one gets cancelled. But Let's say the array is arranged as [1,2,3,4,5 1,2,3,4,5,6]. Then the cumulative xor of the first five elements should be able to keep [the information] for all these five numbers, so that they get cancelled, one by one, after the 6th element. How is that possible?

• ## In fact, it does't keep all the information; 1^2^3 equals 0001^0010^0011=0011^0011=0 you may see these numbers in this way:

``````1    0001
2    0010
3    0011
4    0100
1    0001
2    0010
3    0011
4    0100
5    0101
0345----(trans odd to 1, even to 0)--→0101=5
``````

now you can see, to every bit, pair numbers give it 2 signs and contribute a 0, the number which appear only once will be "left" in the end.

• Xor is both associative and commutative, so you can reorder at will and still get the same result. The result of 1^2^3^4^5^1^2^3^4^5^6 is the same as 1^1^2^2^3^3^4^4^5^5^6.

You're certainly familiar with that from addition, where you're not surprised that 1+2+3+4+5+1+2+3+4+5+6 is the same as 1+1+2+2+3+3+4+4+5+5+6.

• Thanks a lot! Very good explanation. I love XOR now!

• Thanks for a different explanation. That makes totally sense!

• Nice one! Thx!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.