题目:

一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

解题思路:

• 这题目强调一个（或两个）数字只出现一次，其他的出现两次。这有什么意义呢？我们想到异或运算的一个性质：任何一个数字异或它自己都等于0。也就是说， 如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了。

• 想明白怎么解决这个简单问题之后，我们再回到原始的问题，看看能不能运用相同的思路。我们试着把原数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现两次。如果能够这样拆分成两个数组， 我们就可以按照前面的办法分别找出两个只出现一次的数字了。

• 我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消了。由于这两个数字肯定不一样，那么异或的结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1 。我们在结果数字中找到第一个为1的位的位置，记为第n 位。现在我们以第n位是不是１为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第n 位都是1 ， 而第二个子数组中每个数字的第n 位都是0。

• 由于我们分组的标准是数字中的某一位是1 还是0 ， 那么出现了两次的数字肯定被分配到同一个子数组。因为两个相同的数字的任意一位都是相同的，我们不可能把两个相同的数字分配到两个子数组中去，于是我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。我们已经知道如何在数组中找出唯一一个只出现一次数字， 因此到此为止所有的问题都已经解决了。

实现代码

#import <Foundation/Foundation.h>


/**
 找到 第一个 位 为1 位索引

 @param num 异或 之后的数
 @return 位索引
 */
int findFirstOneBit (int num) {
    int tmpIndex = 0;
    while ((num & 1) == 0 && tmpIndex < 32) {
       num = num >> 1;
        
       tmpIndex++;
    }
    return tmpIndex;
}


/**
 判断 当前数组num 在位索引 位置 是否 为1

 @param num 数字
 @param indexBit 位索引
 @return 返回 是否
 */
BOOL isBitOne (int num, int indexBit){
    num = num >> indexBit;
    return (num & 1) == 1;
}

/**
 找到 数组 中 只出现 一次 的数字

 @param numArray 数组
 @param numLength 数组 长度
 */
void findNumbersAppearanceOnce(int *numArray, int numLength) {
    
    int result[2]  = {0, 0};

    
    
    if (numArray == NULL) {
        return ;
    }
    if (numLength == 0) {
        return ;
    }
    
    int xorValue = 0;
    // 将 所有的值 进行异或
    for (int tmpIndex = 0; tmpIndex < numLength; tmpIndex++) {
        xorValue ^= numArray[tmpIndex];
    }
    
    // 找到 抑或 之后 第一位 位值为1的 下标 索引
    int indexOfOne = findFirstOneBit(xorValue);
    
    // 将 数组 分成 两部分
    for(int tmpIndex = 0; tmpIndex < numLength; tmpIndex++){
        if (isBitOne(numArray[tmpIndex], indexOfOne)) {
            result[0] ^= numArray[tmpIndex];
        }
        else {
            result[1] ^= numArray[tmpIndex];
        }
    }
   
    for (int tmpIndex = 0; tmpIndex < 2; tmpIndex++) {
        printf("%d ", result[tmpIndex]);
    }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int data1[8]  = {2, 4, 3, 6, 3, 2, 5, 5};
         findNumbersAppearanceOnce(data1, 8);
    }
    return 0;
}