Chapter1: 位运算的奇技淫巧

2. 题解：如何找数组中唯一成对的那个数

题目

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助空间，能否实现。

算法

需要辅助空间

使用一个1001个元素的数组f，f[i] 记录数字 [i] 出现的次数，f[i]!=1 的 i 即为要找的数

不需要辅助空间

思路：

只有一个数是出现两次的，联想到 ^ 异或运算中，两个相同的数 异或 得到 0 ， 0 和一个数 异或 这个数不变

设题目中的数组为 arr , 让 arr 与1-1000共1000个数 异或, 这样除了 arr 中重复了两次那个数得到保留外，其它的数均变为0，输出这个数即可

核心代码：

int N=1001;
int x1=0;
for(int i=1;i<=N-1;i++){
    x1=(x1^i);//1-1000进行异或
}
for(int i=0;i<N;i++){
    x1=(x1^arr[i]);//1-1000异或的结果与arr的元素进行异或
}
printf("%d\n",x1);

完整代码：

#include<iostream>
#include<cstdlib>
#include<time.h>
using namespace std;

int main(){
    
    int N=11;
    int arr[N];
    for(int i=0;i<N-1;i++){
        arr[i]=i+1;
    }
    
    srand((unsigned)time(NULL));//设置随机数种子 
    arr[N-1] = rand()%(N-1)+1;//产生[1-1000]的随机数，rand()函数产生[0,RAND_MAX]的随机数 

    int result=0;  
    for(int i=1;i<=N-1;i++){//将[1,1000]共1000个数进行异或 
        result^=i;
    }
    for(int i=0;i<N;i++){//再与题意中的数组每个元素进行异或 
        result^=arr[i];
    }
    printf("%d\n",arr[N-1]);
    printf("%d\n",result);
    
    return 0;
}