【答案解析】给定一个含有n个元素的整型数组array，其中只有一个元素出现奇数次，找出这个元素。
因为对于任意一个数k，有k^k=0，k^0=k，所以将array中所有元素进行异或，那么个数为偶数的元素异或后都变成了0，只留下了个数为奇数的那个元素。
程序示例如下：
#include＜stdio.h＞
int FindElementWithOddCount(int*a,int n)
{
int r=a[0];
for(int i=1;i＜n;++i)
{
r^=a[i];
}
return r;
}
int main()
{
int array[]={1,2,2,3,3,4,1);
int len=sizeof(array)/sizeof(array[0]);
printf("%d/n",FindElementWithOddCount(array,len));
return 0;
}
程序输出结果：
4
引申：由n个元素组成的数组，n-2个数出现了偶数次，两个数出现了奇数次(这两个数不相等)，如何用O(1)的空间复杂度，找出这两个数?
假设这两个数分为a、b，将数组中所有元素异或之后结果为X，因为a!=b，所以x=a^b，且x!=0，判断x中位为1的位数，只需要知道某一个位为1的位数k，如00101100，k可以取2或者3，或者5，然后将x与数组中第k位为1的数进行异或，异或结果就是a或b中的一个，然后用x异或，就可以求出另外一个。
因为x中第k位为1表示a或b中有一个数的第k位也为1，假设为a，将x与数组中第k位为1的数进行异或时，也即将x与a以及其他第k位为1的出现过偶数次的数进行异或，化简即为x与a异或，最终结果即为b。
程序示例如下：
#include＜stdio.h＞
void FindElement(int a[],int length)
{
int s=0;
int i;
int k=0;
for(i=0;i＜length;i++)
{
s=s^a[i];
}
int s1=s;
int s2=s;
while(!(s1&1))
{
s1=s1＞＞1;
k++;
}
for(i=0;i＜length;i++)
{
if((a[i]＞＞k)&1)
s=s^a[i];
}
printf("%d%d/n",s,s^s2);
int main()
{
int array[]={1,2,2,3,3,4,1,5};
int len=sizeof(array)/sizeof(array[0]);
FindElement(array,len);
return 0;
}
程序输出结果
45