1. 異或的理解
我們通常把異或定義為不同為1，相同為0，即如如下真值表所顯示：
| a | b | a ^ b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
但從另外一方面想，我們可以將異或運(yùn)算認(rèn)為是二進(jìn)制的無進(jìn)位相加：
設(shè) a = 10110101
? b = 01011101
則 a ^ b = 11101000
相當(dāng)于每位各自相加但是沒有進(jìn)位。
2. 異或的運(yùn)算性質(zhì)
0 ^ N = N N ^ N = 0
a ^ b = b ^ a (交換律) a ^ b ^ c = a ^ (b ^ c) (結(jié)合律)
同樣的一組數(shù)異或得到的數(shù)一定相同，因?yàn)椴徽撨@組數(shù)怎樣調(diào)換順序、組合，經(jīng)過2中的交換率和結(jié)合律都可以得到相同順序的一組數(shù)。
3. 異或的應(yīng)用
3.1 用于交換兩個數(shù)的變量值
int a = 甲; //假設(shè)a的值為甲，b的值為乙
int b = 乙;
/*下面的程序用于交換兩個數(shù)的值*/
a = a ^ b;
b = a ^ b;
a = a ^ b;
就這樣，a和b的值就已經(jīng)進(jìn)行了交換，是不是有點(diǎn)不可思議！??
下面我們來具體分析一下三步運(yùn)算中a和b的值：
a = a ^ b;a = 甲 ^ 乙 b = 乙b = a ^ b;a = 甲 ^ 乙 b = 乙 ^ 甲 ^ 乙 = 甲 ^ (乙 ^ 乙) = 甲a = a ^ b;a = 甲 ^ 乙 ^ 甲 = (甲 ^ 甲) ^ 乙 = 乙 b = 甲
是不是清楚了很多呢？有沒有覺得這種方法很神奇？??
但這種方法也有一定的限制??，使用時一定要注意這兩個變量是否指向一個內(nèi)存地址?。?！(應(yīng)用到數(shù)組中就是數(shù)組下標(biāo)是否相同)，如果兩個變量指向一個內(nèi)存地址，那么異或操作會將變量的值置為0。
3.2 用于解決奇次數(shù)問題
- 一個數(shù)組中，一種數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)出現(xiàn)了偶數(shù)次，如何找出這個出現(xiàn)奇數(shù)次的數(shù)？
分析：經(jīng)過上面的分析，很容易就想到了用異或的方法，因?yàn)橹挥幸粋€奇數(shù)次數(shù)，其它都是偶數(shù)次數(shù)，如果將數(shù)組中所有數(shù)進(jìn)行異或操作，那么最后剩下的那個數(shù)便是我們所求的奇數(shù)次數(shù)。
解決：定義一個初值為0的變量，分別與數(shù)組中的每個數(shù)異或，最后這個變量中保存的值就是所求的奇數(shù)次數(shù)。
- 一個數(shù)組中，兩種數(shù)出現(xiàn)奇數(shù)次，其他數(shù)出現(xiàn)偶數(shù)次，如何求出這兩個出現(xiàn)奇數(shù)次的數(shù)？
分析：??這下有兩個奇數(shù)次數(shù)了，該怎么辦呢？不慌，讓我們看看這組數(shù)異或后的結(jié)果是什么。
顯然，這組數(shù)異或最后就剩這兩個奇數(shù)次數(shù)了。設(shè)這兩個數(shù)分別為a和b。則異或的最后結(jié)果為a ^ b。因?yàn)槭莾煞N數(shù)，所以a != b，則a ^ b != 0，即a和b至少有一個位上是不同的，a ^ b至少在某一位上為1，由a ^ b的結(jié)果可以求得這個位。將該數(shù)組分成兩種，一種是該位上為1的，另一種是該位上不為1的，則a和b分別位于兩種數(shù)組中。取一個eor'，令其該位置為1其他位置為0，用eor'異或數(shù)組中所有該位上為1的數(shù)，則最后結(jié)果一定為a或b。再將a或b與之前所求的a ^ b在進(jìn)行異或操作，就可以求出另外一個數(shù)。至此，a和b都已求出。
有沒有覺得異或運(yùn)算很神奇呢？??
本人系菜鳥一枚，所寫文章皆為學(xué)習(xí)總結(jié)，大佬請輕噴:??
謝謝閱讀:??，歡迎補(bǔ)充！
