#LeetCode# Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

首先想到的是两层循环，显然不符合线性时间；那先排序再比较呢？引入sort的话，时间复杂度也是nlogn起跳，同样不符合。一层循环，不用额外空间，可愁死人了。

点击TAG有惊喜，TAG显示Hash Table和Bit Manipulation，哈希表好久没碰过，不过位操作让我好奇心大作。位操作不就是&，^，| 这些么？顺手谷歌重新学习下位操作。

C语言提供了六种位运算符：
    &     按位与
    |      按位或
    ^      按位异或
    ~      取反
    <<    左移
    >>    右移 

........

基本可以锁定^ 按位异或 了。

a⊕b = (¬a ∧ b) ∨ (a ∧¬b)

a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c

a ⊕ b ⊕ a = b

enough，我的问题可以解决了，感恩戴德交换律！

手写代码，

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        for(int i=0;i<A.length;i++){
            res=res^A[i];
        }
        return res;
    }
}
Accepted
LOL