1. 什么是異或

兩個二進(jìn)制數(shù)進(jìn)行異或運算時，每一位上的數(shù)相同則結(jié)果為0，不同則結(jié)果為1。

示例：6^7=?

轉(zhuǎn)化成二進(jìn)制：
6=110
7=111
6^7=110^111=001=1

簡單記：異或就是二進(jìn)制的無進(jìn)位相加。
還有個同或運算：相同為1，不同為0，和異或是反的。

2. 異或運算的特性

1. 任何數(shù)與0異或，結(jié)果還是這個數(shù)：0^n=n
2. 任何數(shù)與自身異或，結(jié)果都是0：n^n=0
3. 異或運算滿足交換律和結(jié)合律

這幾個特性按照無進(jìn)位相加的思路來理解，就很好想明白。

3. 異或運算的神奇應(yīng)用

3.1 兩數(shù)交換

兩個數(shù)經(jīng)過3次異或運算后，可以交換位置。這其實也是上面特性的一個應(yīng)用。

a=1; b=3;
a=a^b; // a與b異或后，賦值給a：a=1^3 b=3
b=a^b; // 賦值后的a與b再次異或后，賦值給b：a=1^3 b=1^3^3=1（此時a初始的值已經(jīng)賦給b了）
a=a^b; // 賦值后的a和b再次異或后，賦值給a：a=1^3^1=3 b=1（完成了交換）

以上交換的邏輯，只有在兩個數(shù)指向不同的內(nèi)存塊時，才有效。如果兩個數(shù)，指向同一個內(nèi)存塊，實際上就是1個數(shù)，此時異或后，會得到0。
算法題：https://leetcode.cn/problems/swap-numbers-lcci/description/

3.2 找到出現(xiàn)奇數(shù)次的那個數(shù)

有一組數(shù)，只有一個數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，如何快速找到這個數(shù)？

只要將所有數(shù)都做異或運算，得到的結(jié)果就是那個數(shù)。這是 n^n=0 & 0^n=n 的一個應(yīng)用。

算法題：https://leetcode.cn/problems/single-number/description/

3.3 提取二進(jìn)制數(shù)最右側(cè)的1（與異或無關(guān)）

給定一個二進(jìn)制的數(shù)，找到最右側(cè)的1。例如，二進(jìn)制數(shù)：11001000，最右側(cè)的1對應(yīng)的二進(jìn)制數(shù)為：00001000。

通過公式：n & (～n + 1) 即可得到結(jié)果。

以 11001000 為例：
00110111 // 對n取反:~n
00111000 // 取反后加1:～n + 1
00001000 // 和n進(jìn)行與運算:n & (～n + 1)

取反運算規(guī)則：將二進(jìn)制的每一位逆轉(zhuǎn)，1變成0，0變成1
與運算規(guī)則：僅1&1=1，其他都為0。

應(yīng)用：找出一個二進(jìn)制數(shù)n中一共有多少個1

rightOne = n & (～n + 1) // 找出最右側(cè)的1
n ^= rightOne // n和rightOne異或后，再賦值給n，可以抹掉n最右側(cè)的1
循環(huán)以上兩步直到n=0，數(shù)出一共循環(huán)了多少次即可

算法題：https://leetcode.cn/problems/number-of-1-bits/description/

擴(kuò)展：通過公式 n & (n - 1) 可以抹掉最右側(cè)的1，也可以找出二進(jìn)制數(shù)中有多少個1。

以 11001000 為例：
11000111 // n - 1
11000000 // n & (n - 1)

3.4 找到出現(xiàn)奇數(shù)次的那2個數(shù)

有一組數(shù)，大部分?jǐn)?shù)都出現(xiàn)了偶數(shù)次，只有2個不同的數(shù)出現(xiàn)了奇數(shù)次，如何快速找到這2個數(shù)？

思路：
假設(shè)這兩個數(shù)為a和b，將所有的數(shù)進(jìn)行異或運算，得到的結(jié)果一定是：eor=a^b
eor一定不等于0（因為a!=b）,也就是說eor的二進(jìn)制數(shù)在某一位上一定是1，且這個1一定來源于a和b其中一個數(shù)（因為只有1^0=1）
假設(shè)eor在第8位是1，根據(jù)第8位是1將數(shù)組分成兩組，1組中數(shù)的第8位都是1，2組中數(shù)的第8位都是0，如果a在1組中，那么b一定在2組中
上面兩組數(shù)中，除了a和b以外，其他數(shù)一定出現(xiàn)偶數(shù)次。1組所有數(shù)全部異或一定等于a，同理2組異或等于b
那么，只要得到eor最右側(cè)的1對應(yīng)的數(shù)eor'，再用eor'與最初的數(shù)組的每一個數(shù)進(jìn)行與運算，結(jié)果等于1（或等于1）的全部保留下來進(jìn)行異或運算，一定得到了a或b
再用eor異或上面的結(jié)果，就得到了另一個數(shù)，這樣兩個數(shù)都找到了。

以 [4, 4, 5, 5, 6, 7] 為例（對應(yīng)的二進(jìn)制數(shù)：[0100, 0100, 0101, 0101, 0110, 0111]）：
eor= 4^4 ^ 5^5 ^ 6^7 = 6^7 = 0110^0111 = 0001 // 將所有的數(shù)異或
eor'= 0001 // 找到eor最右側(cè)的1對應(yīng)的數(shù)（通過第3.3小節(jié)的公式可以得到）
array1= [0100, 0100, 0110] // 分成2組數(shù)，這一組和eor'進(jìn)行與運算后都等于0，其他的數(shù)和eor'進(jìn)行與運算后都不等于0
a= 0100 & 0100 & 0110 = 0110 = 6
b= a^eor = 0110 ^ 0001 = 0111 = 7

算法題：https://leetcode.cn/problems/single-number-iii/description/文章來源地址http://www.zghlxwxcb.cn/news/detail-844402.html

到了這里，關(guān)于異或運算在算法中的神奇應(yīng)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！