只出现一次的数字——III
注：本题的解法建立在位运算——异或和题目《只出现一次的数字——I》之上，如果对这些内容不太熟悉，建议先看看：
思路
我们先来回顾一下异或的特性：
异或是支持交换律的：
a ^ b ^ c=b ^ a ^ c
a ^ a = 0（相同的数异或为0）
0 ^ a = a（一个数和0异或得到的还是本身）
a ^ b != 0 (a != b)（不等的数据异或的结果绝对不等于0）
对于这一题，我们先举一个具体的例子[1,2,3,4,5,1,2,3,4,6]，该数组中除了5,6只出现了一次，其余元素都出现了两次。
我们不妨先将所有的元素异或到一起，得到的结果为：5 ^ 6，这时有小伙伴就要问了，这是两个数字的异或呀，怎么能将这两个数字分开，得到最后的结果呢？因此，我们可以将这个数组分成两组，并确保相同的数字在一组，只出现一次的两个数字不在同一组，这样，我们分别异或两个数组的数据，最后得到的不就是两个只出现一次的数据吗？
那么问题又来了，我们怎么确保分组时相同的元素在一组，只出现一次的两个元素不在一组呢？
就拿上面的例子来说，所有数字异或到一起后结果为5 ^ 6，这个结果不为0，那么就说明这个结果的二进制位一定有一位不为0（即一定有一位为1），而异或的计算规则是相异为1，因此我们就可以根据这这一位的不同来区分这两个数据。
实现代码
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* singleNumber(int* nums, int numsSize, int* returnSize){ *returnSize = 2; int* ret = (int*)malloc(sizeof(int) * 2); //申请返回数组的内存 memset(ret, 0, 8); //将数组初始化为0 //先将原数组的所有数据异或，得到结果 int temp = 0; for(int i = 0; i < numsSize; i++) temp ^= nums[i]; //算出只出现一次的两个数据的第pos二进制位不同 int pos = 0; for(int i = 0; i < 32; i++) { if(((temp >> i) & 1) != 0) { pos = i; break; } } //将数据分组，原数组的数据第pos位为1分成一组，为0分成一组 //同时将这两组数分别异或，得到最后结果 for(int i = 0; i < numsSize; i++) { if(((nums[i] >> pos) & 1) != 0) ret[0] ^= nums[i]; else ret[1] ^= nums[i]; } //返回结果 return ret; }
