题目描述：

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

解法：

运用异或运算解题。

在编程语言中，整数都是使用二进制表示的。两个整数的异或运算就是将每一位各自进行异或运算后得到的数。

对于两个相同的数，异或运算的结果为 0。对于两个不同的整数，异或运算的结果中至少有一位为1，因此此结果必不为0。

根据这个性质，对 nums 数组中的所有数字进行异或运算后的结果必然不为0，然后找出异或结果中不为0的某一位，对所有数字中这一位取值的不同分为2组。然后根据异或运算的性质，将这两组分别进行异或运算的结果就是最终的两个数。

代码如下：

#include <stdlib.h>/*** Note: The returned array must be malloced, assume caller calls free().*/
int XOR(int * nums, int n){int i, xor;if(n < 2)return nums[0]; // nums 至少有一个元素xor = nums[0] ^ nums[1];for (i=2; i<n; i++)xor ^= nums[i];return xor;
}
int XOR_with_mark(int * nums, int * mrk, int n){int i, xor = 0;int p = 0, first_index;for(i=0; i<n; i++){if(mrk[i] == 1){if(p == 0)first_index = i;else if(p == 1)xor = nums[first_index] ^ nums[i];elsexor ^= nums[i];p++;}}if(p == 1)xor = nums[first_index];return xor;
}
int* singleNumber(int* nums, int numsSize, int* returnSize){unsigned int xor = (unsigned int)XOR(nums, numsSize);unsigned int temp;int i, j;int * mrk1 = (int *) malloc(numsSize * sizeof(int));int * mrk2 = (int *) malloc(numsSize * sizeof(int));unsigned int one = 1;for(i=0; i < 8 * sizeof(int); i++){temp = xor & (one<<i); // 保留xor第i位上的值，i in [0 31]if(temp != 0){for(j = 0; j<numsSize; j++){if(0 != (unsigned int)(nums[j] & temp))mrk1[j] = 1, mrk2[j] = 0;elsemrk2[j] = 1, mrk1[j] = 0;}break;}}int * result = (int *) malloc(2 * sizeof(int));* returnSize = 2;result[0] = XOR_with_mark(nums, mrk1, numsSize);result[1] = XOR_with_mark(nums, mrk2, numsSize);free(mrk1);free(mrk2);return result;
}