邏輯異或運(yùn)算簡(jiǎn)介

邏輯異或運(yùn)算簡(jiǎn)稱異或。異或，英文為exclusiveOR，縮寫(xiě)成xo。異或（xor）是一個(gè)數(shù)學(xué)運(yùn)算符。它應(yīng)用于邏輯運(yùn)算。異或的數(shù)學(xué)符號(hào)為“⊕”，計(jì)算機(jī)符號(hào)為“xor”。其運(yùn)算法則為：

a⊕b=（?a∧b）∨（a∧?b）

如果a、b兩個(gè)值不相同，則異或結(jié)果為1。如果a、b兩個(gè)值相同，異或結(jié)果為0。

異或也叫半加運(yùn)算，其運(yùn)算法則相當(dāng)于不帶進(jìn)位的二進(jìn)制加法：二進(jìn)制下用1表示真，0表示假，則異或的運(yùn)算法則為：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同為0，異為1），這些法則與加法是相同的，只是不帶進(jìn)位。

邏輯異或運(yùn)算性質(zhì)

1、交換律

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

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

4、自反性AXORBXORB=Axor0=A

異或運(yùn)算最常見(jiàn)于多項(xiàng)式除法，不過(guò)它最重要的性質(zhì)還是自反性：AXORBXORB=A，即對(duì)給定的數(shù)A，用同樣的運(yùn)算因子（B）作兩次異或運(yùn)算后仍得到A本身。這是一個(gè)神奇的性質(zhì)，利用這個(gè)性質(zhì)，可以獲得許多有趣的應(yīng)用。例如，所有的程序教科書(shū)都會(huì)向初學(xué)者指出，要交換兩個(gè)變量的值，必須要引入一個(gè)中間變量。但如果使用異或，就可以節(jié)約一個(gè)變量的存儲(chǔ)空間：設(shè)有A，B兩個(gè)變量，存儲(chǔ)的值分別為a，b，則以下三行表達(dá)式將互換他們的值表達(dá)式（值）：

A=AXORB（aXORb）

B=BXORA（bXORaXORb=a）

A=AXORB（aXORbXORa=b）

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

邏輯異或運(yùn)算怎么算

邏輯異或運(yùn)算簡(jiǎn)稱異或。英文為exclusiveOR，或縮寫(xiě)成xor。

異或（xor）是一個(gè)數(shù)學(xué)運(yùn)算符。它應(yīng)用于邏輯運(yùn)算。異或的數(shù)學(xué)符號(hào)為“⊕”，計(jì)算機(jī)符號(hào)為“xor”。其運(yùn)算法則為：

a⊕b=（?a∧b）∨（a∧?b）

如果a、b兩個(gè)值不相同，則異或結(jié)果為1。如果a、b兩個(gè)值相同，異或結(jié)果為0。

異或邏輯

邏輯表達(dá)式：F=AB’⊕A’B（（AB’⊕A’B）’=AB⊙A’B’，⊙為“同或”運(yùn)算）

異或邏輯的真值表如圖1所示

示，其邏輯符號(hào)如圖2所示。異或邏輯的關(guān)系是：當(dāng)AB不同時(shí)，輸出P=1；當(dāng)AB相同時(shí)，輸出P=0?！皑挕笔钱惢蜻\(yùn)算符號(hào)，異或邏輯也是與或非邏輯的組合，其邏輯表達(dá)式為：

P=A⊕B

由圖1可知，異或運(yùn)算的規(guī)則是

0⊕0=0，0⊕1=1

1⊕0=1，1⊕1=0

口訣：相同取0，相異取1

事實(shí)上，XOR在英文里面的定義為eitherone（isone），butnotboth，也即只有一個(gè)為真（1）時(shí)，取真（1）。

邏輯異或運(yùn)算應(yīng)用

1-1000放在含有1001個(gè)元素的數(shù)組中，只有唯一的一個(gè)元素值重復(fù)，其它均只出現(xiàn)一次。每個(gè)數(shù)組元素只能訪問(wèn)一次，設(shè)計(jì)一個(gè)算法，將它找出來(lái)；不用輔助存儲(chǔ)空間，能否設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)？

解法一、顯然已經(jīng)有人提出了一個(gè)比較精彩的解法，將所有數(shù)加起來(lái)，減去1+2+.。.+1000的和。

這個(gè)算法已經(jīng)足夠完美了，相信出題者的標(biāo)準(zhǔn)答案也就是這個(gè)算法，唯一的問(wèn)題是，如果數(shù)列過(guò)大，則可能會(huì)導(dǎo)致溢出。

解法二、異或就沒(méi)有這個(gè)問(wèn)題，并且性能更好。

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

但是這個(gè)算法雖然很簡(jiǎn)單，但證明起來(lái)并不是一件容易的事情。這與異或運(yùn)算的幾個(gè)特性有關(guān)系。

首先是異或運(yùn)算滿足交換律、結(jié)合律。

所以，1^2^.。.^n^.。.^n^.。.^1000，無(wú)論這兩個(gè)n出現(xiàn)在什么位置，都可以轉(zhuǎn)換成為1^2^.。.^1000^（n^n）的形式。

其次，對(duì)于任何數(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(mén)

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

T^（T^n）=n。

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

當(dāng)然有人會(huì)說(shuō)，1+2+.。.+1000的結(jié)果有高斯定律可以快速計(jì)算，但實(shí)際上1^2^.。.^1000的結(jié)果也是有規(guī)律的，算法比高斯定律還該簡(jiǎn)單的多。

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

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