# Leetcode 解題速記 136. Single Numbers
###### tags: `LeetCode` `C++`
題敘:
---
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.

測資範圍:
---
* 1 <= nums.length <= 3 * 104
* -3 * 104 <= nums[i] <= 3 * 104
* Each element in the array appears twice except for one element which appears only once.

解題筆記:
---
沒有複雜度限制的話用迴圈就可以AC
要符合 linear runtime complexity的話嘗試使用Bitwise XOR來判斷

Bitwise XOR : 從位元尺度逐一檢查並用XOR邏輯運算，回傳二進位
運算符: ^
運算特性:
1. A^A = 0
2. A^0 = A
3. A^B = B^A

例:

[2,2,1]
 2^2^1 (law 1)=> 0^1 (law 3)=> 1^0 (law 2) => 1 #result
 
[4,1,2,1,2]
 1^4^2^1^2   
 1^4^1^2^2
 .
 .           (law 3)
 .
 .
 1^1^2^2^4   (按照大小排列)
 0^2^2^4     (law 1)
 0^0^4
 0^4         (law 2)
 4           #result
 

程式碼
---

int n = nums[0];
for (int i = 1; i < numsSize; i++){
    n^=nums[i];
}
return n;