How it works:
if you have two integers, x and y, x^y will return an integer such that each bit will be 0 if the corresponding bits from x and y are the same, and 1 if they are different. This leads to two properties: z = x^x == 0, because every bit is the same, and z = x^0 == x, because when nth bit of x is 1, it is different from 0, therefor the nth bit of z is 1, and when the nth bit of x is 0, it is the same as 0, therefor the nth bit of z is 0.
Ex:
5^4 = 0b101^0b100 = 0b001 = 1 <-- only the last bit is different
7^9 = 0b0111^0b1001 = 0b1110 = 14 <-- the first three bits are different
7^0 = 0b111^0b000 = 0b111 = 7 <--only the bits that are 1 (all three) are different
8^0 = 0b1000^0b0000 = 0b1000 = 8 <-- only the bits that are 1 (the first) are different
6^6 = 0b110^0b110 = 0b000 = 0 <-- no bits are different
So, if you traverse an array, and xor each item with the cumulative xor of the previous, any duplicates will cancel out:
int nums[5] = {1,1,2,2,3};
int i, x = 0;
for(i = 0; i < 5; i++)
x = x^nums[i];
cout << x << endl;
results in:
x = 1^1^2^2^3 = (1^1)^(2^2)^3 = 0^0^3 = 0^3 = 3
Note: this will work so long as 1) there is only ONE unique number (otherwise, it will return the xor of all unique elements), and 2) any duplicate elements have an even number of elements (they cancel out in pairs, and any remaining numbers would 'pollute' the output)