一个数组中只有一个数是唯一的，其他数都是成对出现，找出这个唯一的数
要求时间复杂度为o(n),空间复杂度为o(1)
分析：由于位运算符异或运算的特点，即两个相同的数进行异或运算时，其结果为0，所以当将数组中所有的元素进行异或运算时，其结果必定为那个唯一的数。
代码如下：
int findOnlyNum(int arr[], int len) {
int result = 0;
for (int i = 0; i < len; i++)
{
result = result ^ arr[i];
}
return result;
}
一个数组中有两个数是不同的，其他数都是成对出现，找出这两个不同的数
要求时间复杂度为o(n),空间复杂度为o(1)
分析：当两个数不同时，其二进制位必定有一位是不同的，我们可以找出这个二进制位，并将数组分成两个子数组，保证每个数组中只有一个数是唯一的，这样就会变成问题一的情况。
代码实现如下：
void findTwoDifNums(int arr[], int len, int& num1, int& num2) {
int sum = 0;
for (int i = 0; i < len; i++)
{
sum ^= arr[i];
}
int firstBit = findFirstBit(sum);
for (int i = 0; i < len; i++)
{
int num = arr[i] >> firstBit;
if (num & 1)
{
num1 ^= arr[i];
}
else
{
num2 ^= arr[i];
}
}
}
int findFirstBit(int num) {
int firstBit = 0;
//注意这里有个容易出错的地方，由于位运算符的优先级低于等号，所以必须对 num & 1加括号，
//若写成 num & 1 == 0,则是错误的，其结果是无法进入while循环。
while (((num & 1) == 0) && (firstBit < 8 * sizeof(int)))
{
num = num >> 1;
firstBit++;
}
return firstBit;
}
测试代码如下：
void main() {
int arr[9] = { 2, 3, 4, 9, 4, 3, 9, 2, 8 };
int value = findOnlyNum(arr, sizeof(arr) / sizeof(int));
cout << "The different value is " << value << endl;
int arr2[10] = { 2, 3, 4, 9, 6, 4, 3, 9, 2, 8 };
int num1 = 0;
int num2 = 0;
findTwoDifNums(arr2, sizeof(arr2) / sizeof(int), num1, num2);
cout << "The different two values is " << num1 <<" "<<num2 << endl;
getchar();
}
运行结果如下：
image.png
引自： 《剑指offer》
