题目：整型数组中除了两个数字之外，其他的数字都出现两次，找出这两个只出现一次的数字
思路：利用异或运算的性质：任何一个数字异或自己都等于0；
1.从头到尾依次异或数组中的每个数字，最终得到的结果就是两个只出现一次的数字的异或结果；
2. 异或结果的二进制表示中至少有一位为1，找到结果数字中第一个为1的位的位置，记为第n位；
3. 以第n位是否为1为标准把原数组中的数字分为两个子数组，第一个子数组中的每个数字的第n位都为1，
第二个子数组中的每个数字的第n位都为0；
4. 最后分别对两个子数组进行异或运算，就可以求出两个只出现一次的数字
代码如下：
#include "stdafx.h"
#include <iostream>
using namespace std;//整型数组中除了两个数字之外，其他的数字都出现两次，找出这两个只出现一次的数字
//要求：时间复杂度O(n)，空间复杂度：O(1)
//判断在num的二进制表示中从右边数起的indexBit位是否为1
bool IsBit1(int num, int indexBit)
{num = num >> indexBit; return (num & 1);
}//在num的二进制表示中找到最右边是1的位
int FindFirstBitIs1(int num)
{int indexBit = 0;while ((num & 1) == 0){num = num >> 1;indexBit++;}return indexBit;
}void FindNumsAppearOnce(int nArr[], int nLength, int &num1, int &num2)
{if (nArr == NULL || nLength < 2){return;}int nResultExlusiveOR = 0;//记录数组中所有数进行异或之后的结果for (int i=0; i<nLength; i++){nResultExlusiveOR ^= nArr[i];}int indexBit = FindFirstBitIs1(nResultExlusiveOR);//找到异或结果的二进制表示中最右边1的位置//根据该位上为1或0将原数组分为两部分，然后对两部分数字分别进行异或运算，得到的两个数即为所求for (int j=0; j<nLength; j++){if (IsBit1(nArr[j], indexBit)){num1 ^= nArr[j];}else{num2 ^= nArr[j];}}
}int _tmain(int argc, _TCHAR* argv[])
{int nArr[8] = {2,4,3,6,3,2,5,5};int nNum1 = 0;int nNum2 = 0;FindNumsAppearOnce(nArr, 8, nNum1, nNum2);cout << "只出现一次的数字为：" << nNum1 << " " << nNum2 << endl;system("pause");return 0;
}运行结果：
