How does using XOR to find a single element with odd number of occurrences in an array work?

Consider this problem:

You are given an array containing positive integers. All the integers occur even number of times except one. Find this special integer.

Solution:

The integer with the odd number of occurrences will have 0 or more pairs and one single number. So, if we could some how get rid of all the pairs th开发者_Go百科en all we'd be left with is the single number. Now, what gets rid of pairs? Hint: think of an operator.

XOR will do the trick. Its gives you O(n) solution with no extra memory.

int GetSpecialOne(int[] array, int length)
{
    int specialOne = array[0];

    for (int i=1; i < length; i++)
    {
        specialOne ^= array[i];
    }

    return specialOne;
}

I don't understand how reducing the array by accumulating the XOR on each element produces the special integer. How does it work?

---

It works because (N xor Q) xor Q = N.

Exactly one integer is present an odd number of times, so it will be the only number not to "disappear" from the list. All other numbers are present an even number of times so they all appear in groups of 2's (conceivably), so they all "disappear". Also, the "distance" between the XORs don't matter: (((N xor Z) xor Q) xor Z) xor Q = N. The Z's and the Q's "cancel out" even though there are intermediate XORs between the pairs.

---

The XOR operator has the property that (a ^ a) == 0, and (by extension) that (a ^ b ^ a) == b. Therefore, any value that occurs an even number of times will "cancel" out to zero in the XOR "accumulation", leaving just the odd one out.

---

Fact one: x XOR x is zero.

This follows from the fact that 0 XOR 0 is zero and 1 XOR 1 is zero.

Fact two: x XOR x XOR x ... x is zero where x appears an even number of times.

This follows from fact one by induction.

Fact three: x XOR x XOR x ... x is x where x appears an odd number if times.

This follows from fact two by writing the expression as

(x XOR x XOR x ... x) XOR x = 0 XOR x = x

where there are 2n terms in the parentheses if there were 2n + 1 terms in the original.

Fact four: XOR is associative and commutative.

This is trivial to verify.

Now it is clear how this code works. The numbers that appear an even number of times are reduced to zero by this code. The sole number that appears an odd number of times is reduced to itself by this code.

---

^ is an exclusive or operator. Both operands to the bitwise exclusive OR operator must be of integral types. The bitwise exclusive OR operator compares each bit of its first operand to the corresponding bit of its second operand. If one bit is 0 and the other bit is 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0.

If both are either high or low, output is 0 and in all other cases output is 1.

Ex: a^b^a^a^b^c^c => ( c^c =0; b^b = 0; a^a = 0; Finally left with 0^0^0^a = a ) . So, the number which is odd times repeated among the even times repetition in the sequence is the output. You can work with the same example, taking the array elements.