题目要求
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。
方法：
- 由于其他数都出现两遍，把这些数异或在一起，结果为0->，所以数组中所有元素异或起来，实际是两个单身狗异或的结果记为ret
- 由于两个单身狗不相同，所有异或的结果至少有1个比特位为1 (异或特点：对应比特位，相同为0，不同为1)
- 所以可以对ret逐位判断，找到为1的比特位所在的位置进行分组。pos：两个比特位不同的位置（即异或的结果对应的比特位为1的位置：可任意位置，只要对应比特位为1即可）
- 把数组中所有元素的pos位为1的放在一组，把pos位为0的放在另一组。认为最低位是第0位
图解
选择二进制序列中的哪一个比特位为1进行分组没有关系，只要是选择异或结果的二进制序列中某一位为1的进行分组即可
代码
>> 左移 << 右移
int main() { int arr[] = {1,1,2,5,6,5,7,8,7,8}; int sz = sizeof(arr)/sizeof(arr[0]); int ret = 0; int i = 0; //将数组中的所有元素进行异或，得到的结果就是两个单身狗异或的结果 for(i = 0;i<sz;i++) { ret^=arr[i]; } //得到ret的二进制序列中比特位为1的位置 int pos = 0; for(i = 0;i<32;i++) { //ret不断左移i位，与1相与，如果结果为1，说明该比特位为1 if( ( (ret>>i) &1 ) ==1 ) { pos = i; break; } } //将数组元素中二进制序列pos位为1的分到1组中，为0的分到另一组 int m = 0; int n = 0; for(i = 0;i<sz;i++) { if( ( (arr[i] >>pos)&1 )== 1 ) { //pos位置比特位为1和m异或 m ^=arr[i]; } else { //pos位置比特位为0和n异或 n ^= arr[i]; } } printf("%d %d\n",m,n); return 0; } 复制代码
leetcode题目：
链接：剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode） (leetcode-cn.com)
函数接口：
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* singleNumbers(int* nums, int numsSize, int* returnSize){ } 复制代码
思路和上面的基本一致，但是要注意，这个题目要重新开辟一个空间用来保存两个单身狗，所以数组只需开辟两个大小的空间即可。
题目已经明确说明，动态开辟的数组不用我们释放，由调用者自己释放。所以我们只需要返回该数组的起始地址即可！！
注意点：动态开辟的数组的元素最初要初始化为0，否则最初动态开辟的数组的两个元素都是随机值，这样进行分组异或的话就会出错
->为数组元素初始化可以使用：直接使用下标初始化：
e.g. arr[0] = 0 arr[1] = 0
也可以使用memeset()函数进行初始化！
/** * Note: The returned array must be malloced, assume caller calls free(). ->后序我们不用释放，留个使用者释放 */ int* singleNumbers(int* nums, int numsSize, int* returnSize){ int i = 0; int ret = 0; //数组的元素进行异或，得到的结果就是两个单身狗异或的结果 for(i = 0;i<numsSize;i++) { ret ^=nums[i]; } //得到ret的二进制序列中比特位为1的位置pos int pos = 0; for(i = 0;i<32;i++) { //两个单身狗异或结果不断左移，直到找到比特位为1的位置 if( ((ret>>i)&1) == 1 ) { pos = i; break; } } //将数组元素比特位pos位置为1的分到一组，为0的分到另一组进行异或 //开辟数组用来存储两个单身狗 int* newarr = (int*)malloc(sizeof(int)*2); //注意：数组元素要初始化为0，否则不能通过，得到的是随机值 newarr[0] = 0; newarr[1]= 0; for(i = 0;i<numsSize;i++) { //元素比特位pos位置为1的和数组第一个元素异或，为0的和数组第二个元素异或 if( ((nums[i]>>pos)&1) == 1) { newarr[0] ^=nums[i]; } else { newarr[1] ^=nums[i]; } } //要返回数组中所含元素 ，让用户得知数组的元素个数。 *returnSize = 2; return newarr; } 复制代码
好了，今天就到这儿吧，欢迎大佬们点赞、收藏、评论呀！笔者水平有限，欢迎各位大佬批评指正！再次感谢！
