Java中異或的深入講解

前言

異或是一種基于二進制的位運算，用符號XOR或者 ^ 表示，其運算法則是對運算符兩側(cè)數(shù)的每一個二進制位，同值取0，異值取1。

性質(zhì)

1、交換律

2、結(jié)合律（即(a^b)^c == a^(b^c)）

3、對于任何數(shù)x，都有x^x=0，x^0=x

4、自反性 A XOR B XOR B = A XOR 0 = A

異或運算最常見于多項式除法，不過它最重要的性質(zhì)還是自反性：A XOR B XOR B = A，即對給定的數(shù)A，用同樣的運算因子（B）作兩次異或運算后仍得到A本身。這是一個神奇的性質(zhì)，利用這個性質(zhì)，可以獲得許多有趣的應(yīng)用。 例如，所有的程序教科書都會向初學者指出，要交換兩個變量的值，必須要引入一個中間變量。但如果使用異或，就可以節(jié)約一個變量的存儲空間： 設(shè)有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;

 類似地，該運算還可以應(yīng)用在加密，數(shù)據(jù)傳輸，校驗等等許多領(lǐng)域。

應(yīng)用舉例：1-1000放在含有1001個元素的數(shù)組中，只有唯一的一個元素值重復(fù)，其它均只出現(xiàn)一次。每個數(shù)組元素只能訪問一次，設(shè)計一個算法，將它找出來；不用輔助存儲空間，能否設(shè)計一個算法實現(xiàn)？

解法一、顯然已經(jīng)有人提出了一個比較精彩的解法，將所有數(shù)加起來，減去1+2+...+1000的和。這個算法已經(jīng)足夠完美了，相信出題者的標準答案也就是這個算法，唯一的問題是，如果數(shù)列過大，則可能會導(dǎo)致溢出。

解法二、異或就沒有這個問題，并且性能更好。將所有的數(shù)全部異或，得到的結(jié)果與1^2^3^...^1000的結(jié)果進行異或，得到的結(jié)果就是重復(fù)數(shù)。

但是這個算法雖然很簡單，但證明起來并不是一件容易的事情。這與異或運算的幾個特性有關(guān)系。首先是異或運算滿足交換律、結(jié)合律。

所以，1^2^...^n^...^n^...^1000，無論這兩個n出現(xiàn)在什么位置，都可以轉(zhuǎn)換成為1^2^...^1000^(n^n)的形式。
其次，對于任何數(shù)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的所有數(shù)的異或）。
令，1^2^...^1000（序列中不包含n）的結(jié)果為T

則1^2^...^1000（序列中包含n）的結(jié)果就是T^n。

T^(T^n)=n。

所以，將所有的數(shù)全部異或，得到的結(jié)果與1^2^3^...^1000的結(jié)果進行異或，得到的結(jié)果就是重復(fù)數(shù)。

當然有人會說，1+2+...+1000的結(jié)果有高斯定律可以快速計算，但實際上1^2^...^1000的結(jié)果也是有規(guī)律的，算法比高斯定律還該簡單的多。

google面試題的變形：一個數(shù)組存放若干整數(shù)，一個數(shù)出現(xiàn)奇數(shù)次，其余數(shù)均出現(xiàn)偶數(shù)次，找出這個出現(xiàn)奇數(shù)次的數(shù)？

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);
}

解法有很多，但是最好的和上面一樣，就是把所有數(shù)異或，最后結(jié)果就是要找的，原理同上??！

************************************分割線*******************************************

這樣可以實現(xiàn)不引人第三個變量實現(xiàn)交換，但是進行的計算相對第三個變量多，所以效率會低一些。

關(guān)于其他的方法還有：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

但是這樣做有一個缺陷，假設(shè)它運行在vc6環(huán)境中，那么int的大小是4 Bytes，所以int變量所存放的最大值是2^31-1即2147483647，如果我們令a的值為2147483000，b的值為1000000000，那么a和b相加就越界了。

事實上，從實際的運行統(tǒng)計上看，我們發(fā)現(xiàn)要交換的兩個變量，是同號的概率很大，而且，他們之間相減，越界的情況也很少，因此我們可以把上面的加減法互換，這樣使得程序出錯的概率減少：

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看做數(shù)軸上的點，圍繞兩點間的距離來進行計算。

具體過程：第一句“a-=b”求出ab兩點的距離，并且將其保存在a中；第二句“b+=a”求出a到原點的距離（b到原點的距離與ab兩點距離之差），并且將其保存在b中；第三句“a+=b”求出b到原點的距離（a到原點距離與ab兩點距離之和），并且將其保存在a中。完成交換。

下面順便介紹交換兩個數(shù) 的三種方法：

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對億速云的支持。