本文主要是介绍数据结构与算法：异或的妙用（找出一堆数中唯一/唯二出现奇数次的项、swap的优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
异或的本质是相同为0，不同为1，实际上也就是无进位加法。
那么对于任何数x和y，以下公式永远成立
x^0=x
x^x=0
(x^y)^x=x^(y^x)=(x^x)^y=0^y=y//交换律和结合律
也就是说一堆数里面，出现偶数次的项先自己异或，那么就会得0，然后再和出现奇数次的项进行异或，那么最终结果就是自己本身。
找出一堆数中唯一/唯二出现奇数次的项
找出一堆数中唯一出现奇数次的项
如果一堆数中，只有一个数出现了奇数次，其他数都出现了偶数次，如何快速的找出这个数。
我们只需要将这堆数逐一异或，那么最后出来的结果就是这个数。
时间复杂度为O（N），空间复杂度为O（1）
public static void printOddTimesNum1(int[] arr){int eor=0;for(int cur:arr){eor^=cur;}System.out.println(eor);
}
找出一堆数中唯二出现奇数次的项
如果一堆数中，只有a和b出现了奇数次，其他数都出现了偶数次，如何快速的找出a和b。
（不需要找出a和b分别是多少，但是要找出a和b这一对）
我们只需要将这堆数逐一异或，那么最后出来的结果就是a^b，记作eor
在eor的二进制表示中，一定至少存在一位为1，因为a和b不相同，那么异或出来的二进制至少有一位为1，我们记这位为第x位。
那么要么是a在这第x位上为1，要么是b在这第x位上为1.在这我们就假设是a为1。
且一堆数中出现偶数次的项也分为两大部分，要么在这第x位上为1，要么在这第x位上为0。
无论怎样，这一堆数整体会分为两大部分，在这第x位上为1的分类A（包含a），和在这第x为上为0的分类B
我们取这最右侧一位1和分类A的数逐一异或，得到的就是第x位上为1的a（因为假设a在第x位上为1）然后a再与eor异或，就得到b了。
时间复杂度为O（N），空间复杂度为O（1）
public static void printOddTimesNum2(int[] arr){int eor=0;for(int i=0;i<arr.length;i++){eor^=arr[i];}int rightOne=eor&(~eor+1);int onlyOne=0;for(int cur:arr){if((cur&rightOne)==1){//也可以改为==0，那么最终得到的就是分类BonlyOne^=cur;}}System.out.println(onlyOne+" "+(eor^onlyOne));}
具体如何提取该数二进制最右侧的1
int a
int rightone = a & (~a+1)
swap的优化
往常swap的代码为：
int temp=a;
a=b;
b=temp;
但是通过异或操作，我们可以省去这额外的一个常数空间。代码如下：
a=a^b;
b=a^b;
a=a^b;
但是注意，a和b一定要是不同的地址，否则就相当于自己和自己异或，会直接变为0
所以，假设a原本存储着信息x，b原本存储着信息y
a=a^b；即，a变为x异或y，b仍为y
b=a^b；即，b变为(x异或y)异或y，即b变为x，a仍为x异或y
a=a^b；即，a变为(x异或y)异或x，即a变为y，b仍为x
本篇文章还是不懂的话可以去看https://www.bilibili.com/video/BV13g41157hK
这篇关于数据结构与算法：异或的妙用（找出一堆数中唯一/唯二出现奇数次的项、swap的优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
