// 面试题56（一）：数组中只出现一次的两个数字

// 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序

// 找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

#include <iostream>

unsigned int FindFirstBitIs1(int num);

bool IsBit1(int num, unsigned int indexBit);

void FindNumsAppearOnce(int data[], int length, int* num1, int* num2)

{

    if (data == nullptr || length < )//判断边界

        return;

    int resultExclusiveOR = ;

    for (int i = ; i < length; ++i)//讲究，0异或任何一个数就等于那个数，三个数连续异或，若两个一样的，会抵消，剩下的值就是第三个数

        resultExclusiveOR ^= data[i];

    unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);//求出这组数里，某位为1

    *num1 = *num2 = ;

    for (int j = ; j < length; ++j)//以此位为标志，分为两个数组，每个数组都有且只有一个数字，其个数为奇数

    {

        if (IsBit1(data[j], indexOf1))

            *num1 ^= data[j];

        else

            *num2 ^= data[j];

    }

}

// 找到num从右边数起第一个是1的位

unsigned int FindFirstBitIs1(int num)

{

    int indexBit = ;

    while (((num & ) == ) && (indexBit <  * sizeof(int)))

    {

        num = num >> ;//向右移1位

        ++indexBit;

    }

    return indexBit;

}

// 判断数字num的第indexBit位是不是1

bool IsBit1(int num, unsigned int indexBit)

{

    num = num >> indexBit;

    return (num & );

}

// ====================测试代码====================

void Test(const char* testName, int data[], int length, int expected1, int expected2)

{

    if (testName != nullptr)

        printf("%s begins: ", testName);

    int result1, result2;

    FindNumsAppearOnce(data, length, &result1, &result2);

    if ((expected1 == result1 && expected2 == result2) ||

        (expected2 == result1 && expected1 == result2))

        printf("Passed.\n\n");

    else

        printf("Failed.\n\n");

}

void Test1()

{

    int data[] = { , , , , , , ,  };

    Test("Test1", data, sizeof(data) / sizeof(int), , );

}

void Test2()

{

    int data[] = { ,  };

    Test("Test2", data, sizeof(data) / sizeof(int), , );

}

void Test3()

{

    int data[] = { , , , , ,  };

    Test("Test3", data, sizeof(data) / sizeof(int), , );

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    system("pause");

    return ;

}