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

   “一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字？”这是经典的算法题，乍看这个题的思路特别多。

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

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\n",num1);
        printf("second data is %d\n",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。

   还是存在这个问题，如果这三个元素异或以后的值刚好为零，这种方法不能解决了，因此采用异或解决只有一个不成对或者两个不同元素的问题是没有问题的，对于三个元素具有一定的可行性，但是不一定时时成立。

   异或运算在算法中针对的问题也是特定的，主要是这种元素成对出现的问题，如果不成对出现，这种算法的实用性能会大大的降低，即使是重复元素都不一定是实用的。