“一个整型数组里除了两个数字之外，其他的数字都呈现了两次。请写程序找出这两个只呈现一次的数字？”这是经典的算法题，乍看这个题的思路特别多。
比方首要排序、然后在查找不同的数据就能找到这两个数字，这种完成办法的时刻杂乱度应该是在O(NlgN)，由于比较排序的算法最好的时刻杂乱度便是这样。可是乍一看，这题就处理了，可是还没有充沛运用一个条件，绝大多数元素是成对呈现的，这个条件的效果是什么呢？ 当然还有的思路便是hashmap完成，这种完成办法便是选用hash表存储每个变量的次数，最终遍历hash表即可，可是这种办法也存在问题，假如存在负数，或许数组元素的值特别大，选用Hashmap完成的空间杂乱度太大，并不是咱们需求的处理办法，hashmap合适的办法是在必定规模类的数值进行核算。上面这两种办法或许是比较快速想到的。
这道题的完成办法许多，关键是找到最好的完成办法很难，本文就介绍选用异或运算完成这道标题的解法。
异或运算是C语言中位运算的一种操作，这种操作关于嵌入式程序员或许比较了解，可是关于一般的程序员或许运用的比较少，异或操作具有如下的特征：
0^num = num; 1^num = ~num; num ^ num = 0; 其间num = 0或许1。
运用结合律等特征有：
a^a^b^b^c = (a^a)^(b^b)^c=0^0^c=c;
需求留意：假如有a + b = c; 则有或许使得a ^ b ^ c = 0;这个条件对错充沛非必要，比方a = 1，b = 2， c = 3，这时候的a ^ b ^ c = 0是建立的，可是a = 2, b = 2, c = 4,则是不建立的。
从上面的结合律能够知道假如两个相同的数进行异或操作成果是0，依据标题中元素是成对呈现的，能够充沛运用异或操作的结合特性，数组元素异或今后的成果肯定会包括两个不成对元素的特征。
假定数组元素为a[N],其间N的值很大，不成对的元素为an,am。完成上述进程的过程如下所示：
首要，变量元素对一切元素进行异或操作，得到的成果肯定是an^am。也就说经过异或操作今后，成果中保存了an和am的特征。由于am和an不同，am^an的成果肯定是大于等于1。am和an不同，那么am^an中为1的某一个bit肯定是am或许an中某一个的特征。
然后，界说两个值num1，num2，别离用来核算an、am，挑选am^an中的某一个bit作为特征位，假定是第K位是特征位，再次对元素进行遍历，假如元素的第K位是1，这个元素或许是am或许an，那么将当时元素与num1进行异或操作，假如元素的第K为不为0，那么这个元素则或许是另一个值，那么将当时元素与num2进行异或操作。这样遍历完一切元素，由于大部分数据成对呈现，依据异或运算的特征，num1，num2就别离保存了两个不同的值。
由上面的剖析可知，这种算法只需求遍历两次数组空间即可完成数据的断定，这样时刻杂乱度为O(N),一起由于没有hashmap之类的结构体，这样空间杂乱度便是O(1)。这种算法的完成肯定是最佳的。比较前面说到的hashmap、排序算法时刻杂乱度和空间杂乱度都要小，因而这种算法的完成应该是最佳的。
代码完成如下：
#include
#include
int whichbitone(int in)
{
int i = 0;
while((in & (1 << i)) == 0)
i ++ ;
return i;
}
int isbitone(int in, int k)
{
if((in & (1 << k)) != 0)
return 1;
else
return 0;
}
void xortest(int *array, int size)
{
int dxor = 0, xor = 0;
int i = 0, j = 0;
int num1 = 0, num2 = 0;
for(i = 0; i < size; ++ i)
dxor ^= array[i];
if(dxor != 0)
{
j = whichbitone(dxor);
for(i = 0; i < size; ++ i)
{
if(isbitone(array[i],j) == 1)
num1 ^= array[i];
else
num2 ^= array[i];
}
/*得到榜首个数*/
printf(“first data is %d”,num1);
printf(“second data is %d”,num2);
}
}
int main(int argc, char *argv[])
{
int array[10] = {1,2,3,4,7,2,3,1,4,9};
xortest(array,10);
return 0;
}
上面的代码基本上完成了上面的描绘。
关于本题的另一个改换“数组中元素成对呈现，可是存在三个不成对的元素，怎么快速的找出这三个元素？”
这个题看起来和本题有必定的联络性，乃至我以为咱们能够选用相同的办法找出三个值，可是后来发现这种办法存在一个问题，可是三个的状况要远远比两个的杂乱，由于其间存在的或许性要多许多，不是不是归于这个元素便是另一个元素的问题，尽管这种解法或许导致问题发生，可是仍是有或许处理的，除了当三个元素的异或成果为0，即x^y^z = 0时，这种办法是不建立的。
关于三个不同元素的找份，我以为主要是找到其间的一个元素，然后将这个元素移除，在进行上述的别的两个元素寻觅。当然咱们首要扫除三个数据异或为零的特殊状况。详细的完成能够参阅http://blog.csdn.net/zzran/article/details/8108787。
仍是存在这个问题，假如这三个元素异或今后的值刚好为零，这种办法不能处理了，因而选用异或处理只要一个不成对或许两个不同元素的问题是没有问题的，关于三个元素具有必定的可行性，可是不必定不时建立。
异或运算在算法中针对的问题也是特定的，主要是这种元素成对呈现的问题，假如不成对呈现，这种算法的有用功能会大大的下降，即使是重复元素都不必定是有用的。
