给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

分析：
我们先来回忆一个学过的符号”^”，异或，运算法则：
a ^ b = c

a b c
1 1 0
1 0 1
0 1 1
0 0 0

一句话总结：相同为 0，不同为 1

我们来看一个实例：
98 ^ 33 =？
98 对应的二进制表示是：1100010
33 对应的二进制表示是：0100001

1 1 0 0 0 1 0
0 1 0 0 0 0 1
1 0 0 0 0 1 1

故答案为 1000011，换算回十进制 67
所以： 98 ^ 33 = 67

之所以提这个是因为它的特性”相同为 0”，比如 1 ^ 1 ^ 3 ^ 3 ^ 7 = 7，相同的经过计算就没了，由此可得

class Solution {
    public int singleNumber(int[] nums) {
        int n = 0;
        for (int i = 0; i < nums.length; i++) {
            n ^= nums[i];
        }
        return n;
    }
}

延伸：

异或还有个用途：交换两个数，以前我们都是

void swap(int a,int b){
    int t = a;
    a = b;
    b = t;
}

利用异或，可以：

void swap(int a,int b){
    a = a^b;
    b = b^a;
    a = a^b;
}

还是上面用过的栗子：
假设 a 是 98，b 是 33，
则第一次： a = a ^ b，即 98 ^ 33 = 67，a 变为 67
第二次：b = b ^ a，即 33 ^ 67 = 98，b 变为 98
第三次：a = a ^ b，即 67 ^ 98 = 67，a 变为 33
a b 交换完值