leetcode- Single Number

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?

起初看到题目，不知道怎么做，看了提示说用位运算，马上就有思路了

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int ret = 0;

		for (int i = 0; i < nums.size(); i++)
		{

			ret = ret ^ nums[i];
		}


		return ret;
	}
};



int main(int argc, char *argv[])
{
	Solution s;
	vector<int> v = { 1, 2, 2, 3,1 };
	

	cout << s.singleNumber(v);

	system("pause");
	return 0;
}

同样的原理（^异或运算的性质(满足交换律 结合律)）可完成ab的交换而不利用临时变量,许多hash 函数也利用了该性质 

a=a^b;
b=a^b;
a=a^b;