【Leetcode】只出现一次的数字III

只出现一次的数字III

题目

思路

a^a=0
0^a=a
设需要找的数为A和B，先用0与整个数组异或，得到的结果为A和B的异或C，然后找出C中某个为1的一位，这一位为1说明AB中这一位一个为0，一另个为1，将数组中这一位为1的放一组异或，将数组中这一位为0的放一组异或，得到的结果一个是A，一个就是B

代码实现

int* singleNumber(int* nums, int numsSize, int* returnSize) 
{
    int temp=0;
    for(int i=0;i<numsSize;i++)//第一步：得出这两个数的异或结果
    {
        temp^=nums[i];
    }

    int m=0;
    while(m<32)//找出这两个数异或结果中的任意一位1即可，m表示第m位
    {
        if(temp & (1<<m))
            break;
        else
            m++;
    }

    int x1=0,x2=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i] & (1<<m))//将这一位为1的放在一起异或
        x1^=nums[i];
        else//将这一位为0的放在一起异或
        x2^=nums[i];
    }

    int* retArr=(int*)malloc(sizeof(int)*2);
    retArr[0]=x1;
    retArr[1]=x2;
    *returnSize=2;
    return retArr;
}