Single Number
今天是一道有关位运算的题目，来自LeetCode(#136)，难度为Medium，Acceptance为46.5%。
这类题目不需要太多的算法知识，需要的知识位运算的基础知识和经验。
题目如下
Given an 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 ?
解题思路及代码见阅读原文
思路如下
其实，该题的思路较为简单，只要想到使用位运算就很容易想到。题目中除一个数之外，其他数字都出现两次，可以想到两个相同的数做异或得到了，这样将所有的数做异或就可以得到那个只出现一次的数。
代码如下
java版
public class Solution {
/**
*@param A : an integer array
*return : a integer
*/
public int singleNumber(int[] A) {
int ans = 0;
for(int i : A)
ans ^= i;
return ans;
}
}
c++版
int singleNumber(int A[], int n) {
int result = 0;
for (int i = 0; i<n; i++) {
result ^=A[i];
}
return result;
}
