# # 136 Single Number

[LeetCode](https://leetcode.com/problems/single-number/)

```
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?

input: 一個雙倍出現的數字 + 單獨出現的數字組成陣列
output: 找出那個落單的
```

```
Example 1:

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

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


/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {}
```

### 怎麼解

第一想法就是先排序後再找旁邊的是不是跟你一樣，不一樣就是落單的數字了。但後來看[這篇](https://ithelp.ithome.com.tw/articles/10158350)\
發現用 bitwise operators 可以超快。應用到 ^ 的特性。這題說是兩兩數字出現所以很適合用

**^ (XOR)** 

bit1 ^ bit2 : 當兩個位元一樣時回傳0，不一樣時回傳1。

```
     9 (base 10) = 1001 (base 2)
    14 (base 10) = 1110 (base 2)
                --------------------------------
14 ^ 9 (base 10) = 0111 (base 2) = 7 (base 10)
```

* 交换律：a ^ b ^ c  <=> a ^ c ^ b
* 任何数于0异或为任何数 0 ^ n => n
* 相同的数可以等於 0: n ^ n => 0

```
var singleNumber = function(nums) {
    let result = nums[0];
    for(let i= 1; i< nums.length; i++){
        result = result ^ nums[i]
    }
    return result;
};

console.log(singleNumber([4,1,2,1,2,2]))
```

```
所以  [4,1,2,1,2]
    4 ^ 1 ^ 2 ^ 1 ^ 2
==  1 ^ 1 ^ 2 ^ 2 ^ 4
==  0 ^ 0 ^ 4
==  4 // 答案
```