Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

解析

此題要求從一陣列中找出非成對出現的數字。由於兩個同樣的位元進行XOR運算後會得到0，任何位元與0進行XOR運算後的值都是原值，因此如果有一遮罩的 bit 都是０，則某數與其進行XOR運算後會保持原值。基於這個原理，將陣列中所有的值都進行XOR運算後，最後得到的數字即為此題所求。

解法

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

備註

Java的位元運算有以下四種：

1. 補數運算(~)：進行數值的2補數運算，如下：

     ~  0 1 0 1   運算元1
     =  1 0 1 1   (~運算元1)    –    回傳結果  

2. AND(&)：若兩者皆為１則輸出為１，否則輸出皆為０，如下：

        0 0 1 1   運算元1
   AND  1 0 0 1   運算元2
     =  0 0 0 1   (運算元1 & 運算元2)    –    回傳結果

3. OR(|)：若兩者有一個為１則輸出為１，兩者皆為０則輸出為０，如下：

        0 0 1 1   運算元1
    OR  1 0 0 1   運算元2
     =  1 0 1 1   (運算元1 | 運算元2)    –    回傳結果    

4. XOR(^)：若兩者位元不同則輸出為１，若相同則輸出為０，如下：

        0 0 1 1   運算元1
   XOR  1 0 0 1   運算元2
     =  1 0 1 0   (運算元1 ^ 運算元2)    –    回傳結果

希望透過記錄解題的過程，可以對於資料結構及演算法等有更深一層的想法。
如有需訂正的地方歡迎告知，若有更好的解法也歡迎留言，謝謝。