详细：java异或运算符

女爷i 2022-06-06 09:38 130阅读 0赞

# 目录 #

*  目录
    
     *  性质
     *  应用举例
     *  其他用途示例

--------------------

> 异或是一种基于二进制的位运算，用符号XOR或者^表示，其运算法则是对运算符两侧数的每一个二进制位同值则取0，异值则取1.  
> 简单理解就是不进位加法，如1+1=0，0+0=0，1+0=1.  
> For example: 3^5 = 6  
> 转成二进制后就是 0011 ^ 0101 二号位和三号位都是异值取1 末尾两个1同值取零，所以3^5 = 0110 = 6

## 性质 ##

1、交换律  
2、结合律（即(a^b)^c == a^(b^c)）  
3、对于任何数x，都有x^x=0，x^0=x  
4、自反性 A XOR B XOR B = A xor 0 = A

异或运算最常见于多项式除法，不过它最重要的性质还是自反性：A XOR B XOR B = A，即对给定的数A，用同样的运算因子（B）作两次异或运算后仍得到A本身。这是一个神奇的性质，利用这个性质，可以获得许多有趣的应用。 例如，所有的程序教科书都会向初学者指出，要交换两个变量的值，必须要引入一个中间变量。但如果使用异或，就可以节约一个变量的存储空间： 设有A,B两个变量，存储的值分别为a，b，则以下三行表达式将互换他们的值 表达式 （值） ：  
A=A XOR B (a XOR b)  
B=B XOR A (b XOR a XOR b = a)  
A=A XOR B (a XOR b XOR a = b)

例：

int a = 10, b = 5
    
    a = a ^ b;
    
    b = a ^ b;
    
    a = a ^ b;

类似地，该运算还可以应用在加密，数据传输，校验等等许多领域。

## 应用举例 ##

1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现  
一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空  
间，能否设计一个算法实现？  
解法一、显然已经有人提出了一个比较精彩的解法，将所有数加起来，减去1+2+…+1000的和。  
这个算法已经足够完美了，相信出题者的标准答案也就是这个算法，唯一的问题是，如果数列过大，则可能会导致溢出。  
解法二、异或就没有这个问题，并且性能更好。  
将所有的数全部异或，得到的结果与1^2^3^…^1000的结果进行异或，得到的结果就是重复数。  
但是这个算法虽然很简单，但证明起来并不是一件容易的事情。这与异或运算的几个特性有关系。  
首先是异或运算满足交换律、结合律。  
所以，1^2^…^n^…^n^…^1000，无论这两个n出现在什么位置，都可以转换成为1^2^…^1000^(n^n)的形式。  
其次，对于任何数x，都有x^x=0，x^0=x。  
所以1^2^…^n^…^n^…^1000 = 1^2^…^1000^(n^n)= 1^2^…^1000^0 = 1^2^…^1000（即序列中除了n的所有数的异或）。  
令，1^2^…^1000（序列中不包含n）的结果为T  
则1^2^…^1000（序列中包含n）的结果就是T^n。  
T^(T^n)=n。  
所以，将所有的数全部异或，得到的结果与1^2^3^…^1000的结果进行异或，得到的结果就是重复数。  
当然有人会说，1+2+…+1000的结果有高斯定律可以快速计算，但实际上1^2^…^1000的结果也是有规律的，算法比高斯定律还该简单的多。

google面试题的变形：一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数？

@Test
    public void fun() {
    int a[] = { 22, 38,38, 22,22, 4, 4, 11, 11 };
    int temp = 0;
    for (int i = 0; i < a.length; i++) {
    temp ^= a[i];
    }
    System.out.println(temp);
    }

解法有很多，但是最好的和上面一样，就是把所有数异或，最后结果就是要找的，原理同上！！

--------------------

## 其他用途示例 ##

这样可以实现不引人第三个变量实现交换，但是进行的计算相对第三个变量多，所以效率会低一些。  
关于其他的方法还有：int a=5,b=10;  
a=a+b; //a=15,b=10  
b=a-b; //a=15,b=5  
a=a-b; //a=10,b=5  
但是这样做有一个缺陷，假设它运行在vc6环境中，那么int的大小是4 Bytes，所以int变量所存放的最大值是2^31-1即2147483647，如果我们令a的值为2147483000，b的值为1000000000，那么a和b相加就越界了。  
事实上，从实际的运行统计上看，我们发现要交换的两个变量，是同号的概率很大，而且，他们之间相减，越界的情况也很少，因此我们可以把上面的加减法互换，这样使得程序出错的概率减少：  
int a=5,b=10;  
a -= b; //a=-5,b=10  
b += a; //b=5,a=-5  
a = b - a; //a=10,b=5  
通过以上运算，a和b中的值就进行了交换。表面上看起来很简单，但是不容易想到，尤其是在习惯引入第三变量的算法之后。  
它的原理是：把a、b看做数轴上的点，围绕两点间的距离来进行计算。  
具体过程：第一句“a-=b”求出ab两点的距离，并且将其保存在a中；第二句“b+=a”求出a到原点的距离（b到原点的距离与ab两点距离之差），并且将其保存在b中；第三句“a+=b”求出b到原点的距离（a到原点距离与ab两点距离之和），并且将其保存在a中。完成交换。

感谢原创作者对知识的分享 [转载地址][Link 1]

[关于运算符，二进制，位移运算符和运算符的应用介绍的比较详细的博客][Link 2]

下面这两位博主也都写的很好  
[位运算符的应用1][1]

[位运算符的应用2][2]

[Link 1]: http://www.cnblogs.com/JhSonD/p/6374397.html
[Link 2]: http://nassir.iteye.com/blog/1994914
[1]: http://blog.csdn.net/Dustin_CDS/article/details/50808343
[2]: http://www.cnblogs.com/fuck1/p/5899402.html