异或运算在算法中的经典运用

比如首先排序、然后在查找不同的数据就能找到这两个数字，这种实现方法的时间复杂度应该是在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。