Leetcode260. 只出现一次的数字C语言

leetcode的算法题

这是思路：

1. 将数组中的每一个数都与eor异或，得到eor=a^b，a和b至少有一位不同，假设为第8位
2. 所有的数可以分为两类：第8位是1、第8位是0；a和b一定在不同的类中
3. 令eor'异或第8位是1的数，最终eor'=a/b
4. 故另一个数则为`eor^eor

代码如下：

int * singleNumber(int* nums, int numsSize, int* returnSize){
    int eor = 0, i;
    // 使eor=a^b
    for (i = 0; i < numsSize; i++) {  
        eor = eor ^ (*(nums+i));
    }
    int rightOne = eor & (~eor + 1); //提取出2进制最右边为1的一位
    int onlyOne = 0; // eor'
    for (i = 0; i < numsSize; i++) {
        if ((rightOne & (*(nums+i))) == 0) //找到rightOne那一位为0的那一类
        {
            onlyOne = onlyOne ^ (*(nums+i));
        }
    }
    //找到一个a/b
    int otherOne;
    otherOne = eor ^ onlyOne;  //另一个数
    returnSize[0]=onlyOne;
    returnSize[1]=otherOne;
    return returnSize;

}