## 一.題目描述  ## 二.解題思路 題目提到，一個數組中除了一個數只出現一次之外，其他數都出現了兩次，找出這個特別的數。 這道題對時間和空間有要求，面對這種情況，一般是暗示有十分輕巧而簡便的方法進行求解。在一些場景下，使用基本的邏輯運算是個不錯的選擇。自己簡單寫了一下，再參照網上部分解法，基本都是使用了異或運算(XOR)，**任何數與自己進行按位異或都等于0，而任何數與0進行按位異或都等于本身**。 在C/C++中，按位異或運算符為：“^” 基于以上規則，我們可以將整個數組的元素都按位進行異或，最終返回那個只出現一次的數了。 ## 三.示例代碼 ~~~ // 時間復雜度O(n)，空間復雜度O(1) class Solution { public: int FindSingleNumber(int A[], int n) { int x = 0; for (size_t i = 0; i < n; ++i) x ^= A[i]; // XOR return x; } }; ~~~ ## 四.總結 本題使用了bool運算中的異或，除此之外沒有大的難點，不知是否有更高效的算法。 因為使用到了異或，結合網上相關博文的總結，在這記錄一下異或運算的性質和常見用法，其實這些性質很容易驗證： 一個數和自己做異或的結果是`0`；? 和`0`做異或保持原值不變，和`1`做異或得到原值的相反值；? 如果`a1^a2^a3^…^an`的結果為`1`，則表示`a1`到`an`之中`1`的個數為**奇數**，否則為**偶數**。這一性質可用于奇偶校驗；? `x^x^y == y`，推導很簡單：`x^x == 0`，而?`0^y == y`。這一性質可用于在不允許使用中間變量來交換兩個數的情況下，實現兩個數的交換，如以下swap函數，交換a和b的值： ~~~ void swap(int &a,int &b) { a ^= b; b ^= a; a ^= b; } ~~~ **然而，該辦法并不是沒有漏洞**。如果輸入`a`和`b`的值相等，得到的結果就不是我們想要的，原因如下： ~~~ a ^= a; a ^= a; a ^= a; ~~~ 對自身異或結果自然是`0`了。 因此，將數值交換函數改成以下形式，可避免這種錯誤發生： ~~~ void swap(int &a,int &b) { if(a == b) return; // 防止a，b指向同一個地址 a ^= b; b ^= a; a ^= b; } ~~~