异或的高级用法以及LeetCode刷题

int missingNumber(int* nums, int numsSize)
{
int arr[numsSize];
int i=0;
for(i=0;i<numsSize;i++)
{
    arr[i]=i+1;//先把arr里面赋的是完整的1到n
}
int x=0;
for(i=0;i<numsSize;i++)
{
    x^=arr[i];//0和他们异或之后就是异或1^2^3……^n
}
for(i=0;i<numsSize;i++)
{
    x^=nums[i];//异或之后的1^2^3……^n再和原数组进行异或，之后一样的就都没了，就只剩一个落单的，就是那个消失的数
}
return x;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumbers(int* nums, int numsSize, int* returnSize){
int ret=0;
int i;
//假设出现1次的数是x1和x2
//把所有数都异或
for(i=0;i<numsSize;i++)
{
    ret^=nums[i];
}
//异或完了就是剩下两个数的异或结果
//ret=x1^x2
//下一步就是想办法分离两者
//找出ret里面第m位为1的，说明x1和x2的第m位不一样，一个为1一个为0
//我们在ret里面不好分离，在原数组里面分离x1和x2
//分成两组，第m位位1的位一组
//         第m位为0的为一组
//所以x1，x2一定会分别在这两组里面
//其他数成对出现在某一组，相同的数，那一位肯定相同，肯定都在同一组
int m=0;//因为是在数组里面找第m位，所以把他弄成0
//ret一定不为0，一定有1这一位
while(m<32)//int一共有32位
{
    if(ret&(1<<m))//ret与上1左移m为，如果为1，就找到了那个第m位
    break;
    else
    m++;
}
//
int x1=0,x2=0;
for(i=0;i<numsSize;i++)
{
    if(nums[i]&(1<<m))
    {
     //为1的在一组
     x1^=nums[i];   
    }
    else
    {
    x2^=nums[i];
    }
}
int* returna=(int*)malloc(sizeof(int)*2);
*returnSize=2;
returna[0]=x1;
returna[1]=x2;
return returna;
}

​
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* missingTwo(int* nums, int numsSize, int* returnSize)
{
int ret=0;
int ret1=0;
int i=1;
for(i=1;i<=numsSize+2;i++)
{
ret^=i;
}
for(i=0;i<numsSize;i++)
{
    ret^=nums[i];
}
//此时ret的结果就是剩下两个数异或的结果
int m=0;
while(m<32)
{
if(ret&(1<<m))
{
    break;
}
else
m++;
}
int ret0=0;
int ret2=0;
//先分组做原数组的
for(i=0;i<numsSize;i++)
{
    if(nums[i]&(1<<m))
    {
        ret0^=nums[i];
    }
    else
    ret2^=nums[i];
}
for(i=1;i<=numsSize+2;i++)
{
    if(i&(1<<m))
    {
        ret0^=i;
    }
    else
    ret2^=i;
}
*returnSize=2;
int *retarr=(int *)malloc(sizeof(int)*2);
retarr[0]=ret0;
retarr[1]=ret2;
return retarr;
}
​