亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

Java中異或的深入講解

發布時間:2020-09-14 18:33:03 來源:腳本之家 閱讀:236 作者:甘劭 欄目:編程語言

前言

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

性質

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面試題的變形:一個數組存放若干整數,一個數出現奇數次,其余數均出現偶數次,找出這個出現奇數次的數?

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中。完成交換。

下面順便介紹交換兩個數 的三種方法:

Java中異或的深入講解

總結

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

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

东乌珠穆沁旗| 公主岭市| 龙山县| 多伦县| 德州市| 抚远县| 铜山县| 开原市| 镇安县| 苍溪县| 竹山县| 朝阳县| 保山市| 农安县| 宜宾市| 安溪县| 海晏县| 垣曲县| 郴州市| 临泽县| 江阴市| 巩义市| 灵宝市| 新化县| 钦州市| 革吉县| 堆龙德庆县| 石柱| 德令哈市| 尼勒克县| 宜君县| 林芝县| 南江县| 峡江县| 榆树市| 汉阴县| 夏邑县| 若羌县| 罗田县| 兰坪| 永安市|