最近看了左神的课程，异或运算的应用简直超乎我的想象。
对于异或运算，我的理解是可以把它看作一个奇函数，什么意思呢，就是如果参与异或运算的1有奇数个，那么运算得到的结果就是1，否则就是0。
那么就会有0 ^ a = a; a ^ a = 0，还可以由此得到，异或运算具有结合律和交换律，也就是异或的最终结果和参与异或运算的变量的运算顺序无关。
好，就此拓展，奇数个a异或得到的就会是a本身，偶数个就会是0。
首先是第一个，两个数的交换。
#include <iostream>
void swap(int& a,int& b)
{
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
int main(){
int a = 10;
int b = 15;
swap(a , b);
std::cout << a << " " << b;
return 0;
}
从a = a ^ b开始，现在a的值为a ^ b，记为A,b 的值是b。
之后 b = a ^ b，也就是A ^ b，即 ：b = a ^ b ^ b = a，记为B 。
最后 a = a ^ b，也就是A ^ B，即：a = a ^ b ^ a = b。
此时，就完成了交换。对于这个A和B，只是我为了方便去记录a 和 b 的最新的值以便于后续计算。
第二个，假如说：这里有一个数组，里面有n个数，里面的数据可以按照出现的次数进行分组，出现奇数次的数据只有1个，而出现偶数次的数据有n – 1个。
好，这个时候我想让你使用一个时间复杂度为O(n)，空间复杂度为O(1)的算法来找出这个出现奇数次的数据的值是多少，该怎么解决？
时间复杂度O(n)好满足，但是空间复杂度O(1)不好满足，此时，使用异或运算可以很巧妙的解决。如下：
首先，我们知道异或运算的结果和参与运算的数据的运算顺序无关，那么就不用傻乎乎的给数组排序了，现在我们知道假设一个数a，a ^ a = 0，a ^ a ^ a = a……，也就是奇数个a异或后结果一定是a，而偶数个a异或后结果一定是0。
从这个基础出发，我们假设这个数组里有1,2,3这三个不同的数 ，其中数组内部如下：
int num[] = {1,2,3,1,2,3,1}
那么出现偶数次的2和3就会因为异或运算的奇函数的性质变为0,而出现奇数次的1就会变为自身1，0 ^ 1 = 1，所以就找到了这个数1。
代码如下：
#include <iostream>
//void swap(int& a, int& b)
//{
//a = a ^ b;
//b = a ^ b;
//a = a ^ b;
//}
int main() {
/*int a = 10;
int b = 15;
swap(a, b);
std::cout << a << " " << b;*/
int num[] = { 1, 2, 3, 1, 2, 3, 1 };
int eor = 0;
for (int i = 0; i < sizeof(num) / sizeof(int); i++) {
eor = eor ^ num[i];
}
std::cout << eor;
return 0;
}
现在问题升级，如果这个时候，出现奇数次的数据变为两个又该怎么办？先定为a 和 b。
在此之前，先来补充一个知识点，如果你想找到一个未知的数a最右边的的1（二进制的情况下），你该怎么找？可以a &(~a +1)，就可以得到最右边的1，实践出真知，如果疑惑，不如自己计算一下。
好，接着这个问题，我们还是老套路，数组里的数据都异或一遍，得到的结果是eor = a ^ b，那怎么求出a和b呢，首先我们知道a ^ b != 0，那么它们异或之后的结果的二进制形式，一定有一位不为0，即为1，不妨设为*****1***（这是第四位为1），*代表未知，那么这个时候，我们可以把数组里的数据进行分类，分为第四位为1和第四位不为1，这个很好理解，所有的数二进制情况下，你这个第四位要么为1，要么为0，总不能是2吧？a和b一定只有一个数在第四位为1，奇函数的性质嘛，1和0异或才会是1，很好理解。
好，分类之后：
图中的other1和other2，是指其他出现偶数次的数，只不过被分类了而已，这个时候，我可以先求出这个a ^ b的结果的最右边的1的位置（eor & (~eor + 1)），定义一个eor1，然后用这个数和数组里的数进行按位与运算，来达到分组的效果，之后再让eor1和这个数组里的数异或运算，最终就会得到a 或者 b，然后再用eor ^ eor1来求出另外一个数，口说无凭，还很晦涩，直接看代码:
#include <iostream>
//void swap(int& a, int& b)
//{
//a = a ^ b;
//b = a ^ b;
//a = a ^ b;
//}
int main() {
/*int a = 10;
int b = 15;
swap(a, b);
std::cout << a << " " << b;*/
int num[] = { 1, 2, 3, 1, 2, 3, 1, 4, 4, 2 };
int eor = 0;
for (int i = 0; i < sizeof(num) / sizeof(int); i++) {
eor = eor ^ num[i];
}
int temp = eor & (-eor + 1);//提取出最右侧的1,记作第i位
int eor1 = 0;//eor1是i位置为1的数异或的结果
for (int i = 0; i < sizeof(num) / sizeof(int); i++) {
if (num[i] & temp) {//这样理解，假设temp = 0000100,temp一定只有一位是1
//那么num[i] & temp的结果要么是0，要么是temp
//如果是temp，说明num[i]的第i位也是1，那么就把num[i]异或到eor1中
eor1 = eor1 ^ num[i];
}
}
int eor2 = eor ^ eor1;
std::cout << eor1 << " " << eor2;
return 0;
}
可以听一下左神的课，在B站搜左神，有个82小时左右的课，是关于数据结构和算法的，很不错的课程。
