class Solution
{public:
int singleNumber(vector<int>& nums) {
for(int i = 1; i < nums.size(); ++i) nums[0] ^= nums[i];
return nums[0];
}
};
I will try to explain it here:
the principle of excusive or operation is: if two bits are same, then result is 0, if two bits are not same(0,1 or 1,0) the result is 1. when you have two same numbers, say 9 and 9, the bitwise exclusive or operation: 1001^1001 is 0000.
however, if you introduce another number say 3. we have 9,3,9. which in binary is 1001, 0011, 1001. if we do bitwise exclusive or operation starting from first number, we have:
step 1: 1001^0011 = 1010
step 2: 1010^1001 = 0011
which the result is 3.
the trick of using exclusive or here is that, when you encounter two same number, no matter how far they are apart from each other, excusive or will let them “counteract” each other.
Let me know if you still dont understand.
Chenxuan
Cuichenxuan has made a very clear explanation. The idea is, xor a certain integer twice is equal to xor this integer with 0, which is itself. And it is independent of the sequence, because for the numbers that make even appearances, all the bit either (1)xor with 1 for even times, or (2)xor with 0 for even times, which in both cases will restore the bit to its original state, leaving the only integer that appeared odd times.