# 136 Single Number

實際運用到 bitwise operators 的 ^，值得複習 !!

LeetCode

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) {}

怎麼解

第一想法就是先排序後再找旁邊的是不是跟你一樣，不一樣就是落單的數字了。但後來看這篇 發現用 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 // 答案