C++利用“异或”

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

看到了一个很有意思的解法

  int singleNumber(vector<int> &nums)
{
    int a = 0;
    for (int i : nums)
    {
        a ^= i;
    }
    return a;
}

这个题要想漂亮的解决，首先就要了解“异或”特点

1. 异或可以用来交换两个变量的值，不用申请空间。

int a=5,b=7;
a=a^b;
b=a^b;
a=a^b;
//a=7,b=5

2.两个相同的值进行异或后为0，0与A异或结果为A

int a=7,b=7,c=0;
a^b    //0
a^c    //7

3.异或满足交换律

a^b^c=a^c^b

---

分析

这道题可利用异或的第2和第3个性质，先设定一个初始值a=0，假定这个数列为{A,B,A}，他的算法是将a与每一个数异或，a与A异或后，a=A，之后与B异或，但由于异或满足交换，可以等价于先于第二个A异或，这样根据第二个性质，a=0，a再次与B异或时，a=B，但因为B只有一个，所以就找到了这个唯一的值。

---

，