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;
}

同样的原理（^ 异或运算满足交换律和结合律）还可以用来交换两个变量 a、b 的值，而无需借助临时变量。许多哈希函数也利用了这一性质。

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