[LeetCode]Single Number III

这次我们要找两个数，我们XOR得到的结果就不是我们要找的target number，而是两个target number不同的位，为1的位代表不同，0的位代表相同。我们取其中一个不同的位，根据这个，我们可以把所有数分成两组，而每一组，就变成了Single Number的题目了，我们做两次XOR即可。Linear time，常数空间。这里我们取最低的不同的位，我们有两种方法可以取，解法1：

	class Solution {
	public:
	vector<int> singleNumber(vector<int>& nums) {
	int diff = 0;
	for(auto& num : nums)
	diff ^= num;
	int mask = 1;
	while((diff & mask) == 0)
	mask <<= 1;
	vector<int> res(2, 0);
	for(auto& num : nums)
	{
	if(num & mask)
	res[0] ^= num;
	else
	res[1] ^= num;
	}
	return res;
	}
	};

view raw Single Number III_1.cpp hosted with ❤ by GitHub

直观的方法，从低到高找第一个不为0的位，然后当做mask来对input进行分组。

解法2：

	class Solution {
	public:
	vector<int> singleNumber(vector<int>& nums) {
	int diff = 0;
	for(auto& num : nums)
	diff ^= num;
	diff &= -diff;
	vector<int> res(2, 0);
	for(auto& num : nums)
	{
	if(num & diff)
	res[0] ^= num;
	else
	res[1] ^= num;
	}
	return res;
	}
	};

view raw Single Number III_2.cpp hosted with ❤ by GitHub

这里我们直接用了diff & -diff，而这个结果恰好可以给我们之前求得mask。如果对源码，反码，补码有疑问或者想知道我们为甚用补码存数据的可以参考这一篇文章。那么我们知道计算机存的是补码，那么对于正数来说，补码是其本身，那么取负数之后，补码是除了符号全取反然后加1,。举个例子对于8来说，补码是0000 0000 0000 1000，-8的补码是1111 1111 1111 1000,8 & -8 = 0000 0000 0000 1000，正好给的就是我们之前求得mask。仔细想的话，假设最低为1的位是第k位，那么显而易见高于第k位的位与的结果是0。对于低于k的位，因为都是0，取反之后都为1，然后都加1，又全变成0，直到进位让取反变成0的1位在变成1。所以这可以给我们想要的结果，那么对于0来说这个结论也成立。对于最后一个特殊的数-2^31，因为我们人为规定其补码为1000 0000 0000 0000（想知道原因的可以参考上面贴出来的文章），那么取负数相当于做一次取反加1的操作，最后还是原来的数，所以仍然成立。