异或运算及其应用-查找奇数个数的数字

异或运算功能很强大。用的得当可以提高算法效率。

先说一下异或运算的运算法则：

       1.  a ^ b = b ^ a
　　2. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
　   3. d = a ^ b ^ c 可以推出 a = d ^ b ^ c
       4. a ^ b ^ a = b

  对于性质1，不多说，显而易见的。

  对于性质2和4，这里最近我发现了一个重要的应用，就是可以查找出一组数列中具有奇数个数的数。比如：

题目：有2n+1个数，其中有n个数出现过两次，只有一个数字出现过一次。要求是找出这个数字。

   为了说明性质2和4如何使用，先举个例子：数列{2,3,4,5,6,9,6,3,2,1,5,8,4,5,5,9,8,1,8} 中8有三个，而其他数字都是2个或者2的倍数（即偶数个），那么根据性质3，我们可以得出这样的结论：

(e^e)^(f^f)^x =0^0^0^0^0^0^0^x = x;

   因为a^a = 0，含有偶数个的数字异或运算的值为0, 0^x = x 最后剩下奇数个的数字x。

   这样仅仅用了一次遍历即可找出。算法效率明显提高。

附C++代码：

#include <iostream>

using namespace std;

void main()
{
  int res = 0;
  int var[17] = {2,3,6,5,8,9,7,4,1,5,6,3,2,9,8,1,7};
  for(int i = 0;i<17;i++)
  {
    res^=var[i];
    cout<<res<<endl;
  }
  cout<<"the result is:"<<res<<endl;
}

对于性质3，也是蛮有趣的。这里也用C++代码验证一下：

#include <iostream>

using namespace std;

void main()
{
  int i = 0;
  int res = 0;
  int var1[17] = 

{22,3,68,5,89,9,7,4,117,12,25,3,62,90,85,10,79};
  for( i = 0;i<17;i++)
  {
    res^=var1[i];
    
  }
  cout<<"结果是:"<<res<<endl;
  //上面的结果是16，用16 随便替换以上序列中任意数字，比如

90，//那么结果应当是90
  res = 0;
  int var2[17] =  

{22,3,68,5,89,9,7,4,117,12,25,3,62,16,85,10,79};
  for( i = 0;i<17;i++)
  {
    res^=var2[i];
    
  }
  cout<<"验证结果是:"<<res<<endl;
  //应当是90
}

异或运算蛮有趣的吧！

  good luck!                                  ------yaung