How can xor keep many numbers?


  • 1
    N

    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?


  • 7
    T

    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.


  • 8

    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.


  • 0
    N

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


  • 0
    N

    Thanks for a different explanation. That makes totally sense!


  • 0
    E

    Nice one! Thx!


Log in to reply
 

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