题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

题目要求

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：
2 <= nums.length <= 10000

---

题解

由于题目对时间复杂度和空间复杂度有要求，那么使用两重循环嵌套暴力寻找（时间复杂度为O(n^2)）是不可行的。因此，考虑使用异或操作来实现。

由于相等的两个数按位异或之后的值为0，那么将数组中所有的数字异或操作起来，所得的数就是我们要寻找的两个落单数字的按位异或结果。
例如：

4 ^ 1 ^ 4 ^ 6 => 1 ^ 6
6 对应的二进制： 110
1 对应的二进制： 001
1 ^ 6 二进制： 111

然而，我们只知道异或的结果，无法反推出这两个数。这时，就需要转换一下思路。如果能将这两个数区分开来，即分到两组里，再分别与两组里其它数异或，就可以得出这两个数分别是什么了。例如：

4 1 4 6 5 5分为4 1 4 和 6 5 5 两组。分别异或，4 ^ 1 ^ 4=>1，6 ^ 5 ^5=>6。这时，我们就找到了落单的1和6两个数字。

PS：由于分组规则是一定的，那么重复数字一定会分到同一组，例如两个4不可能处于不同组。

难点在于如何制定分组规则，区分开两个落单数字。
联想一下，当我们对奇偶数进行分组时，用最后一位二进制是否为1来作为规则。那么，我们可以得出：通过 & 运算来判断一位数字不同即可分为两组。
那么如何找出哪一位不同呢？这就可以用上我们刚才求得的异或结果了。

6 对应的二进制： 110
1 对应的二进制： 001
1 ^ 6 二进制： 111

可以看出，对于6和1这两个数而言，任意一位都可以作为区分的依据，因为它们的每一位都不同。即：001、010、100都可以作为区分规则。例如：
6 & 2（即010）=> 010
1 & 2（即010）=> 000
010这个值称为mask。
那么，我们使用 nums[i] & mask == 0 这个判据，就可以将 6 和 1 分入两组了。C语言中，0为假，非0为真，不是非0即1的概念。因此注意一定是 == 0 ，而不是 != 1。

最后，再将两组的异或结果存入函数返回的数组中即可。

代码如下：

#include <stdio.h>
#include <stdlib.h>

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* singleNumbers(int* nums, int numsSize, int* returnSize){
	*returnSize = 2;
	int num = 0;
	for (int i = 0; i < numsSize; i++){
		num ^= *(nums + i);	//先求出异或值
	}
	int mask = 1;
	while ((num & mask) == 0){ //寻找异或值哪一位为1，可以用作mask
		mask <<= 1;
	}
	int a = 0;
	int b = 0;
	for (int i = 0; i < numsSize; i++){
		if ((*(nums + i) & mask) == 0){	//使用mask作为依据对所有数据进行分组
			a ^= *(nums + i);
		}
		else{
			b ^= *(nums + i);
		}
	}
	int* ret = (int *)malloc(8);	//题设注释要求使用动态数组返回
	*(ret) = a;
	*(ret + 1) = b;
	return ret;
}

int main() {

	int nums[6] = { 15, 16, 21, 22, 22, 21 };
	int numSize = sizeof(nums) / sizeof(nums[0]);
	int size1 = sizeof(int)* numSize;
	int returnSize = 0;
	int* returnSizep = &returnSize;

	int* res = singleNumbers(nums, numSize, returnSizep);

	printf("%d\n", *res);
	printf("%d\n", *(res + 1));

	system("pause");
	return 0;
}

这里另外记录2个细节，也是我初次接触LeetCode遇到的问题：
1、注释中assume caller calls free()表示不需要手动释放开辟的空间。由于之前没有接触过caller的概念，起初有些困惑。
2、函数的参数returnSize表示返回的数组的大小，需要在函数中手动设置为2。若没有赋值，会导致输出有误，无法输出如[6,1]，而是只能输出一个]。