算法题：搜索两条单身狗

技术群里有人提出一个算法题：一个Int型数组，里面的每一个数都是成双成对的，只有一个数是单身狗，找出这个数，算法复杂度<= O(n)

思路很简单，通过异或运算就可以找到这个数。

下面，升级版的算法题来了。

一个Int型数组，里面的每一个数都是成双成对的，只有两个可怜的单身狗，找出这个两个数，时间复杂度<= O(n)，空间复杂度 O(1)？
答案见下方。

---

·
·
·
·
·
·
·
我
是
分
割
线
·
·
·
·
·
·
·
·
·
·
·
·

bool FindDog() {

    int a=0;
    int b=0;

    const int length = 12;
    int arr[length] = {1,2,3,4,5,6,810,5,4,3,2,1};

    int aXORb =0;
    for (int i=0; i<length; i++) {
        aXORb ^= arr[i];
    }
    //查找两个单身狗的异或值，如果为0，则说明不存在两条单身狗。
    if( 0 == aXORb){
        printf("数据错误\n");
        return false;
    }

    //假设异或值为 0010100，则提取出 0000100

    int mask = 0x0;
    int flag = 0;
    while (flag < sizeof(int)) {
        mask = 0x1 << flag;
        int AB = aXORb & mask;
        if (AB>0) {
            break;
        } else {
            flag++;
        }
    }

    if( 0 == mask){
        printf("数据错误\n");
        return false;
    }

    //假设掩码为 0000100，则两个结果的右数第3不一致。
    //通过它，我们拆分数组为分别包含两个结果的数组（相同的数必定在同一数组，两个结果必定在不同数组），并分别求值

    for (int i=0; i<length; i++) {
        if (arr[i] & mask) {
            a ^= arr[i];
        }else{
            b ^= arr[i];
        }
    }
    printf("🐶 = %d \n",a);
    printf("🐶 = %d \n",b);
    
    return true;
}