异或运算符
“^” 是异或运算符，异或的规则是转换成二进制比较，相同为0，不同为1.
异或运算符可认为是无进位的二进制相加，如：6^7
如6二进制为:0000 0110
如7二进制为:0000 0111
则6^7=1
异或运算符性质
（1）0^N=N; N^N=0
（2）满足交换律及结合律
简单的算法题
（1）如果一个数组中只有一个数出现了奇数次，剩下的数都出现了偶数次，求这个出现了奇数次的数。
public static void getData(int[] arr) {
int eor=arr[0];
for (int i=1;i<arr.length;i++){
eor^=arr[i];
}
System.out.println(eor);
}
利用N^N=0性质，则所有出现偶数次的数异或结果都为0，遍历数组将所有的数异或，得到的结果即为出现奇数次的数。
（2）如果一个数组中有两个数出现了奇数次，剩下的数都出现了偶数次，求这两个出现了奇数次的数。
public static void getDatas(int[] arr) {
//怎么把一个整型的数提取出最右侧的1
// N N&((~N)+1)
int eor=0;
for (int i=1;i<arr.length;i++){
eor^=arr[i];
}
int rightOne=eor&(~eor+1); //提取出最右侧的1
int onlyOne=0;
for (int i=0;i< arr.length;i++){
if ((arr[i]&rightOne)!=0){
onlyOne^=arr[i];
}
}
System.out.println(onlyOne+" "+(eor^onlyOne));
}
假设出现奇数次的两个数分别为a,b.
1.第一次遍历数组，将所有数异或后的结果即为两个出现了奇数次的数异或的结果，即eor=a^b
2.将一个数按位取反，再加1，并和它本身相与，得到的是这个数最右侧出现1的位置。
一个数： 0101 0000 1111 0010
~： 1010 1111 0000 1101
加1： 1010 1111 0000 1110
&： 0000 0000 0000 0010
即rightOne求出这两个数在右侧某一位上是1，两个数异或在这一位上为1，即证明a和b，这两个数在这一位上不同，即其中一个在这一位上为0.
3.(arr[i]&rightOne)!=0 得到的是数组中在这一位上为1的数。
4.第二次遍历，将数组中在这一位上为1的所有的数相异或，得到的结果即为，在这位上为1，且出现了奇数次的那个数onlyOne。
5.已知异或的结果，已求出其中一个出现奇数次的数，则另一个出现奇数次的数为eor^onlyOne.
(3)如何不用额外变量就交换两个数的值？
public static void swap(int a,int b) {
a=a^b;
b=a^b;
a=a^b;
System.out.println(a);
System.out.println(b);
}
异或运算可实现两个变量值交换，但两个变量必须指向不同的内存空间。如果两个变量指向同一个内存空间，则会报错；
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/185706.html原文链接：https://javaforall.net
