最近在網(wǎng)上翻到一道很經(jīng)典的題一組整數(shù)里每個(gè)數(shù)字都出現(xiàn)了偶數(shù)次只有唯一一個(gè)數(shù)字出現(xiàn)了奇數(shù)次要求把它找出來(lái)。很多人第一反應(yīng)是哈希表數(shù)一遍再遍歷。但如果再加一條限制空間復(fù)雜度必須做到 O(1)局面就立刻不一樣了。標(biāo)準(zhǔn)答案是一行代碼把所有數(shù)字全部異或一遍留下來(lái)的那個(gè)就是答案。這個(gè)解法流傳很廣可你要是追問(wèn)一句“為什么異或一遍就能找到落單的數(shù)”不少人是答不上來(lái)的只能說(shuō)“本來(lái)就是這樣的”。異或確實(shí)是被誤解最多、也被低估最多的運(yùn)算符。我這些年做協(xié)議解析、狀態(tài)機(jī)、圖形處理和性能優(yōu)化幾乎每個(gè)領(lǐng)域都能看到它的影子。這篇文章不想停留在背真值表的層面而是想從運(yùn)算本質(zhì)講到工程習(xí)慣把異或真正講透。內(nèi)容包括它的三種理解方式、幾個(gè)關(guān)鍵數(shù)學(xué)性質(zhì)、常見(jiàn)實(shí)戰(zhàn)場(chǎng)景以及我在代碼里踩過(guò)的坑。為了讓不同基礎(chǔ)的讀者都能跟上我會(huì)把每個(gè)結(jié)論都拆到可直接驗(yàn)證的地步。1. 異或到底在算什么三種理解方式幫我建立直覺(jué)1.1 真值表之后的第一個(gè)誤區(qū)別只記結(jié)論異或的真值表很簡(jiǎn)單任意一位上相同為0、不同為1xyx ^ y000011101110這張表幾乎人人都見(jiàn)過(guò)。但問(wèn)題在于只記住這張表遇到實(shí)際問(wèn)題時(shí)根本不知道往哪個(gè)方向想。我后來(lái)發(fā)現(xiàn)真正有用的不是表本身而是從三個(gè)角度去理解它二進(jìn)制加法、按位比較、邏輯門實(shí)現(xiàn)。三種理解對(duì)應(yīng)三類不同的應(yīng)用場(chǎng)景比死記結(jié)論有用得多。1.2 理解一不帶進(jìn)位的二進(jìn)制加法異或最直觀的數(shù)學(xué)含義就是“模2加法”你可以把它看成二進(jìn)制加法把進(jìn)位直接丟掉。舉個(gè)例子5 3 用二進(jìn)制算是 101 011 1000也就是8。而 5 ^ 3 是 101 ^ 011 110也就是6。為什么差在這因?yàn)樽畹臀?1 1 產(chǎn)生了進(jìn)位異或不管這個(gè)進(jìn)位直接把這一位清零。這個(gè)理解方式在做校驗(yàn)和、加密、數(shù)據(jù)恢復(fù)時(shí)特別重要。很多工程場(chǎng)景里我們關(guān)心的不是“數(shù)值上的和”而是“每一位上是否相同”異或恰好就是這樣一個(gè)逐位運(yùn)算。記住這句話異或是對(duì)齊二進(jìn)制位后逐位做加法、但不往前進(jìn)位。一旦建立起這個(gè)畫面很多公式就不會(huì)覺(jué)得抽象了。1.3 理解二按位比較相同為0、不同為1第二種理解更簡(jiǎn)單把兩個(gè)數(shù)展開(kāi)成二進(jìn)制從右往左逐位比較一樣的位置記0不一樣的位置記1。這就像小時(shí)候玩的“找不同”游戲兩張圖片并排看哪里有差異哪里就標(biāo)出來(lái)。這套直覺(jué)在算法題里非常管用因?yàn)楹芏鄦?wèn)題的本質(zhì)就是“兩組數(shù)據(jù)的差異在哪里”。比如要判斷兩個(gè)二進(jìn)制串有多少位不同直接異或一下結(jié)果里有多少個(gè)1就有多少處差異。這在漢明距離、簡(jiǎn)單糾錯(cuò)、布隆過(guò)濾器的位運(yùn)算里都是基礎(chǔ)操作。我見(jiàn)過(guò)不少寫權(quán)限系統(tǒng)的同學(xué)看到位掩碼就頭暈其實(shí)只要抓住“異或就是找位差異”這個(gè)角度一切都能順下來(lái)。1.4 理解三從邏輯門看異或的本質(zhì)構(gòu)造如果從數(shù)字電路的角度看異或可以拆成兩個(gè)基本邏輯的組合x(chóng) ^ y (x ~y) | (~x y)這個(gè)式子翻譯成人話就是要么 x 為1且 y 為0要么 x 為0且 y 為1兩種情況都能讓輸出為1。你會(huì)看到異或天然表達(dá)了一種“二選一但是只能選一個(gè)”的邏輯。這也是為什么它在條件切換、分支判斷、狀態(tài)機(jī)設(shè)計(jì)里頻繁出現(xiàn)。很多講位運(yùn)算的資料都略過(guò)這一層直接跳到應(yīng)用但我覺(jué)得理解邏輯門構(gòu)成能幫你一眼看穿它的性質(zhì)異或的輸出和輸入之間是對(duì)稱的、可逆的。因?yàn)槭阶颖旧韺?duì) x 和 y 完全對(duì)稱交換兩個(gè)輸入結(jié)果不變。這為后面的“交換律”和“自反性”打下了直覺(jué)基礎(chǔ)。2. 三條數(shù)學(xué)性質(zhì)為什么異或能把數(shù)據(jù)“變回來(lái)”2.1 異或的自反性不是魔術(shù)是代數(shù)推導(dǎo)異或之所以能解決那么多問(wèn)題核心在于三條性質(zhì)交換律a ^ b b ^ a結(jié)合律(a ^ b) ^ c a ^ (b ^ c)自反性a ^ a 0a ^ 0 a其中交換律和結(jié)合律意味著一堆數(shù)做異或順序完全無(wú)所謂可以隨便重新排列分組。自反性則是最神奇的一條一個(gè)數(shù)與自身異或得0與0異或保持自身。這兩條合起來(lái)就推出了一個(gè)關(guān)鍵推論a ^ b ^ a (a ^ a) ^ b 0 ^ b b也就是一個(gè)數(shù)異或兩次同一個(gè)數(shù)會(huì)變回原來(lái)的自己。這不是魔術(shù)只是代數(shù)推導(dǎo)。你把它想成“按了兩下同一個(gè)開(kāi)關(guān)”第一下開(kāi)燈第二下關(guān)燈最終狀態(tài)不變。這個(gè)“兩次操作互相抵消”的特性是整個(gè)異或應(yīng)用的基石。2.2 和其它運(yùn)算對(duì)比為什么異或的逆運(yùn)算就是它自己加法有對(duì)應(yīng)的減法乘法有對(duì)應(yīng)的除法而異或的“逆運(yùn)算”就是異或本身。這意味著什么如果你想撤銷一次操作不需要額外保存什么狀態(tài)只要把同樣的值再異或一次即可。這在很多場(chǎng)景里能省掉一個(gè)變量、一個(gè)步驟甚至一條指令。我舉個(gè)生活中的類比假如你在一張紙上寫了一個(gè)數(shù)字想擦掉重來(lái)通常需要把紙翻面或重新寫。而異或更像一個(gè)“可逆的開(kāi)關(guān)賬本”你記一筆再記同一筆兩項(xiàng)就互相抵消。所以加密解密、畫了又擦的圖形操作、校驗(yàn)糾錯(cuò)全都建立在它的自反性上。2.3 單位元與零元以及它們對(duì)算法復(fù)雜度的意義0 在異或運(yùn)算里扮演著“單位元”的角色任何數(shù)與0異或都等于它自己。所以在做累積異或時(shí)我們通常把初始值設(shè)為0然后逐個(gè)往里面異或所有元素。因?yàn)?不會(huì)污染結(jié)果最后得到的數(shù)字就能保留所有有效信息。順帶一提在布爾代數(shù)和代數(shù)結(jié)構(gòu)里異或構(gòu)成一個(gè)阿貝爾群。這個(gè)說(shuō)法聽(tīng)起來(lái)嚇人實(shí)際含義卻很樸素參與運(yùn)算的元素可以任意交換位置、任意加括號(hào)而且每個(gè)元素都有自己的逆元它自己運(yùn)算結(jié)果永遠(yuǎn)在一個(gè)封閉集合里。正因?yàn)榻Y(jié)構(gòu)這么好異或才成為哈?；煜z錯(cuò)碼、密碼算法中的常客。理解到這一層你再去看那些“一行搞定”的位運(yùn)算題就不會(huì)覺(jué)得是靈光一現(xiàn)而是有明確的數(shù)學(xué)依據(jù)。3. 實(shí)戰(zhàn)場(chǎng)景一交換變量、簡(jiǎn)單加密與數(shù)據(jù)恢復(fù)3.1 不使用臨時(shí)變量的交換看起來(lái)很酷但要注意陷阱異或最出名的應(yīng)用之一是不用臨時(shí)變量交換兩個(gè)整數(shù)a a ^ b; b a ^ b; a a ^ b;我來(lái)逐步推導(dǎo)一下。設(shè)初始 a 5b 3。第一步后a 變成 5 ^ 3 6。第二步b 6 ^ 3 5此時(shí) b 已經(jīng)等于原來(lái)的 a。第三步a 6 ^ 5 3a 變成了原來(lái)的 b。三行代碼完成交換。這個(gè)技巧在網(wǎng)上很流行但我要提醒你它有一個(gè)非常隱蔽的坑——如果 a 和 b 指向同一個(gè)內(nèi)存地址比如 C 語(yǔ)言里用數(shù)組下標(biāo)操作 a[i] 和 a[j]并且 i j那么 a 先變成0b 也跟著變成0最后數(shù)據(jù)就丟了。我在 C 語(yǔ)言里吃過(guò)這個(gè)虧后來(lái)每次用這套寫法必然先判斷兩個(gè)下標(biāo)是否相同。更關(guān)鍵的問(wèn)題是這個(gè)寫法真的值得用嗎在大數(shù)交換上現(xiàn)代編譯器對(duì)臨時(shí)變量做優(yōu)化之后性能和異或?qū)懛ㄏ嗖顭o(wú)幾而且可讀性更好。異或交換真正有優(yōu)勢(shì)的是寄存器極度受限的嵌入式場(chǎng)景或教學(xué)演示。日常業(yè)務(wù)代碼里我會(huì)毫不猶豫選擇臨時(shí)變量。這不是說(shuō)異或沒(méi)用而是說(shuō)工具的選用要看上下文炫技式寫法不是工程智慧。3.2 簡(jiǎn)單異或加密加密和解密用的是同一把鑰匙異或的自反性讓加密和解密變得極其簡(jiǎn)單。比如要對(duì)一個(gè)字節(jié)流做簡(jiǎn)單加密可以選一個(gè)密鑰 key對(duì)每個(gè)字節(jié)做 plain ^ key得到密文。解密時(shí)只需把密文再異或同一個(gè) keyplain bhello key 0x1F cipher bytes([p ^ key for p in plain]) # 加密 decoded bytes([c ^ key for c in cipher]) # 解密 print(cipher) # 輸出 bwzsso 之類 print(decoded) # 輸出 bhello原理就是前面那條性質(zhì)plain ^ key ^ key plain。如果 key 是個(gè)固定單字節(jié)那么每個(gè)字節(jié)都是同樣的變換這在現(xiàn)實(shí)世界里非常脆弱。只要收集足夠多的已知明文就能猜出 key 的規(guī)律。所以不要把這種異或加密用于真正的敏感數(shù)據(jù)保護(hù)它更適合做簡(jiǎn)單混淆、協(xié)議中的防誤讀、或者僅供學(xué)習(xí)理解密碼學(xué)的臺(tái)階。3.3 RAID中的數(shù)據(jù)恢復(fù)思路多塊硬盤如何互相備份這是異或在工程領(lǐng)域最讓我驚嘆的應(yīng)用之一。簡(jiǎn)單說(shuō)在某種廉價(jià)磁盤冗余陣列方案里數(shù)據(jù)不是單純地復(fù)制一份放在第二塊盤上而是把多塊盤的數(shù)據(jù)做異或生成一份校驗(yàn)數(shù)據(jù)。假設(shè)有 D1、D2、D3 三份數(shù)據(jù)塊校驗(yàn)塊 P D1 ^ D2 ^ D3。如果 D2 那塊盤壞了可以從 D1、D3 和 P 把 D2 恢復(fù)出來(lái)D2 D1 ^ D3 ^ P用剛才的例子驗(yàn)證一下D1 0xA5D2 0x5AD3 0xC3那么 P 0xA5 ^ 0x5A ^ 0xC3 0x3C。如果 D2 丟了算一下 D1 ^ D3 ^ P 0xA5 ^ 0xC3 ^ 0x3C逐位運(yùn)算后確實(shí)得回 0x5A。這種做法的本質(zhì)是校驗(yàn)數(shù)據(jù)不是簡(jiǎn)單地復(fù)制原數(shù)據(jù)而是所有原數(shù)據(jù)的“疊加簽名”任何一份失蹤都能由其他人合力還原。你可以這樣理解三兄弟各自記了一本賬同時(shí)還把三本賬的差異匯總成一張公共卡。任何一本賬丟了另外兩本加上公共卡就能重寫出來(lái)。明白這個(gè)思想再去看分布式存儲(chǔ)里的糾刪碼、容災(zāi)系統(tǒng)的恢復(fù)策略都會(huì)有熟悉感因?yàn)榈讓舆壿嬕幻}相承。4. 實(shí)戰(zhàn)場(chǎng)景二算法題里的?？鸵约氨澈蟮慕y(tǒng)一模式4.1 找唯一出現(xiàn)奇數(shù)次的數(shù)字一行代碼的解釋回到開(kāi)頭的那個(gè)問(wèn)題。假設(shè)數(shù)組是 [4, 1, 2, 1, 2]我們要找4。代碼可以寫成def single_number(nums): result 0 for num in nums: result ^ num return result把它展開(kāi)來(lái)看result 最后等于 4 ^ 1 ^ 2 ^ 1 ^ 2。因?yàn)楫惢驖M足交換律和結(jié)合律可以重新排成 (1 ^ 1) ^ (2 ^ 2) ^ 4。1 ^ 1 得02 ^ 2 得00 ^ 0 ^ 4 得4。所有出現(xiàn)偶數(shù)次的數(shù)字都兩兩抵消歸零而那個(gè)只出現(xiàn)一次的數(shù)字因?yàn)橹槐划惢蛞淮尉土袅讼聛?lái)。這道題背后藏著一個(gè)很通用的思想成對(duì)出現(xiàn)的數(shù)據(jù)可以互相抵消。當(dāng)你需要在一堆數(shù)據(jù)里找“不對(duì)稱的那一個(gè)”異或往往是最省空間的解法時(shí)間 O(n)空間 O(1)。相比之下哈希表雖然思路直接卻要開(kāi)辟額外空間。當(dāng)然哈希表能處理更一般的“統(tǒng)計(jì)頻次”問(wèn)題異或只能處理“成對(duì)抵消”模型二者不是替代關(guān)系。4.2 找缺失的數(shù)字異或與數(shù)學(xué)方法的殊途同歸有一個(gè)經(jīng)典問(wèn)題0 到 n 這 n1 個(gè)數(shù)字里少了一個(gè)找出它。常見(jiàn)的數(shù)學(xué)解法是把 0 到 n 的和減去數(shù)組總和得出缺失值。但用異或也有簡(jiǎn)潔的思路def missing_number(nums, n): x 0 for i in range(n 1): x ^ i for v in nums: x ^ v return x第一輪讓 x 等于 0 到 n 全部值的異或第二輪再把數(shù)組里現(xiàn)存的數(shù)字也異或進(jìn)去。于是所有現(xiàn)存數(shù)字等價(jià)于被異或了兩次全部抵消唯獨(dú)缺失的那個(gè)數(shù)只出現(xiàn)了一次最終留存在 x 里。數(shù)學(xué)求和法需要小心大數(shù)溢出而異或逐位運(yùn)算則沒(méi)有這個(gè)顧慮在嵌入式等場(chǎng)景里更穩(wěn)。4.3 進(jìn)階兩個(gè)數(shù)只出現(xiàn)一次怎么把它們分別找出來(lái)這是我認(rèn)為最能體現(xiàn)異或思維深度的一道題。數(shù)組里有兩個(gè)數(shù)只出現(xiàn)一次其余都出現(xiàn)兩次要求找出這兩個(gè)數(shù)。先全體異或得到 diff這實(shí)際上是那兩個(gè)數(shù)的異或結(jié)果。因?yàn)閮蓚€(gè)數(shù)不同diff 至少有一位是1。接著找到 diff 最低的為1的那一位用它作為分界把數(shù)組分成兩組該位為0的一組、該位為1的一組。由于那兩個(gè)數(shù)在這一位上不同必然被分到不同組而其余成對(duì)的數(shù)在同一組內(nèi)依然成對(duì)繼續(xù)各自異或就能分別得到這兩個(gè)數(shù)。def single_numbers(nums): diff 0 for num in nums: diff ^ num lowbit diff -diff a 0 b 0 for num in nums: if num lowbit: a ^ num else: b ^ num return a, b以 [2, 3, 2, 4, 3, 6] 為例4 和 6 只出現(xiàn)一次。全體異或 diff 4 ^ 6 2。lowbit 是 2也就是二進(jìn)制第二位。把第二位為1的數(shù)分到一組為0的分到另一組4 和 6 恰好分開(kāi)各自組內(nèi)抵消后得到它們。這道題的關(guān)鍵在于異或不僅能找到“異常的那個(gè)”還能通過(guò)某一位的差異把異常者拆開(kāi)。很多復(fù)雜位運(yùn)算題的套路都是這樣先用異或找到線索再利用線索分組最后分別求解。4.4 這類題型的統(tǒng)一口訣兩兩抵消落單自現(xiàn)把上面三道題放在一起你會(huì)發(fā)現(xiàn)它們共享同一個(gè)思維模型數(shù)據(jù)中有大量成對(duì)出現(xiàn)的信息這些信息在異或面前會(huì)互相湮滅真正需要關(guān)注的永遠(yuǎn)是“沒(méi)被抵消”的那部分。遇到算法題先問(wèn)自己三個(gè)問(wèn)題哪些數(shù)據(jù)是成對(duì)出現(xiàn)的成對(duì)的數(shù)據(jù)是否可以通過(guò)異或抵消抵消之后剩下的信息代表了什么這不是死記題型而是一種識(shí)別模式的能力。當(dāng)你看到“尋找唯一出現(xiàn)一次”“尋找缺失數(shù)字”“成對(duì)抵消”等關(guān)鍵詞時(shí)異或應(yīng)該自動(dòng)進(jìn)入你的候選方案列表。不是說(shuō)每次都要用它而是至少先過(guò)一遍這個(gè)思路再?zèng)Q定是否換更復(fù)雜的方法。5. 工程實(shí)戰(zhàn)位掩碼切換、集合對(duì)稱差與圖形學(xué)中的異或5.1 用異或切換狀態(tài)位比判斷后賦值更干凈實(shí)際項(xiàng)目里異或最樸素的工程用途是狀態(tài)切換。假設(shè)你用位掩碼管理權(quán)限或開(kāi)關(guān)一個(gè) flag 本身是 0b1010想翻轉(zhuǎn)其中某一位可以直接flag flag ^ mask # mask 里哪一位是1哪一位就被翻轉(zhuǎn)比如 flag 0b1010mask 0b0010一次異或后變 0b1000再一次異或又變回 0b1010。傳統(tǒng)寫法要判斷當(dāng)前位是0還是1再?zèng)Q定置位還是清零異或?qū)懛ㄖ苯臃D(zhuǎn)不需要分支判斷代碼更短在分支預(yù)測(cè)失效的場(chǎng)景下還更省時(shí)間。我做過(guò)一個(gè)簡(jiǎn)單的狀態(tài)開(kāi)關(guān)模塊原本要用四五個(gè) if 判斷換成異或后邏輯少了一小半可讀性反而提高了因?yàn)榭创a的人一眼就知道這是“翻轉(zhuǎn)”。5.2 位圖表示下的集合對(duì)稱差權(quán)限與標(biāo)簽篩選的利器如果你用位圖表示一個(gè)集合那么兩個(gè)集合的對(duì)稱差屬于A但不屬于B或?qū)儆贐但不屬于A正好對(duì)應(yīng)位圖的異或。這個(gè)性質(zhì)在標(biāo)簽系統(tǒng)、權(quán)限系統(tǒng)里非常實(shí)用。假設(shè)用戶 A 有權(quán)限位 0b1100用戶 B 有權(quán)限位 0b1010那么兩者權(quán)限的差異就是 0b0110哪些權(quán)限不一致一目了然。我做標(biāo)簽篩選時(shí)也常用這個(gè)思路兩個(gè)集合做對(duì)稱差能得到“兩邊標(biāo)簽分布不一致”的對(duì)象列表。當(dāng)然如果你的需求是求交集或并集那要分別用與和或只有當(dāng)你關(guān)心“差異”時(shí)異或才是那個(gè)最自然的運(yùn)算符。區(qū)分清楚需求就不會(huì)用錯(cuò)。5.3 圖形學(xué)里的橡皮筋效果畫了又擦全靠自反性這可能是異或最優(yōu)雅的工程應(yīng)用之一。在圖形界面里拖動(dòng)鼠標(biāo)畫臨時(shí)矩形、調(diào)整選區(qū)時(shí)希望圖形能隨鼠標(biāo)移動(dòng)動(dòng)態(tài)更新同時(shí)不破壞底下的原有內(nèi)容。做法是把繪圖模式設(shè)為 XOR第一次用掩碼畫圖形像素被異或疊加第二次在原位置再畫一遍所有像素恢復(fù)原樣。這樣就不需要保存和重繪整個(gè)背景只需要記住上次的圖形位置。這背后用的正是“異或兩次恢復(fù)原狀”。我記得早期很多圖形工具拖動(dòng)光標(biāo)、橡皮筋框選都采用這個(gè)策略。現(xiàn)在 GPU 渲染管線和窗口系統(tǒng)的處理方式更復(fù)雜但在某些輕量級(jí)圖形庫(kù)、低端嵌入式顯示、老式終端模擬器里這種技巧依然有用。它讓我意識(shí)到理解一個(gè)運(yùn)算的數(shù)學(xué)性質(zhì)是真的能在意想不到的地方派上用場(chǎng)。5.4 協(xié)議幀的異或校驗(yàn)和輕量但要知道它的邊界寫網(wǎng)絡(luò)協(xié)議或串口通信時(shí)經(jīng)常需要加一個(gè)校驗(yàn)字節(jié)確保數(shù)據(jù)在傳輸過(guò)程中沒(méi)被改壞。最簡(jiǎn)單可靠的校驗(yàn)和之一就是把所有字節(jié)逐個(gè)異或frame bytes([0xAA, 0x01, 0x02, 0x03]) checksum 0 for b in frame: checksum ^ b # 0xAA ^ 0x01 0xAB # 0xAB ^ 0x02 0xA9 # 0xA9 ^ 0x03 0xAA發(fā)送端把 checksum 追加在幀尾接收端對(duì)整幀重新異或一遍。如果結(jié)果是0說(shuō)明所有字節(jié)在傳輸過(guò)程中異常的概率很低。它能檢測(cè)單比特翻轉(zhuǎn)因?yàn)槿魏我晃蛔兞俗罱K異或結(jié)果就不是0。但它有一個(gè)著名弱點(diǎn)如果某位在傳輸中被翻轉(zhuǎn)兩次翻轉(zhuǎn)會(huì)互相抵消校驗(yàn)就發(fā)現(xiàn)不了。所以要求更高的場(chǎng)景會(huì)改用 CRC 這類更復(fù)雜的校驗(yàn)算法。不是異或校驗(yàn)不能用而是你要清楚它的能力邊界在安全關(guān)鍵場(chǎng)景里選擇對(duì)應(yīng)強(qiáng)度的方案。6. 邊界條件與常見(jiàn)誤區(qū)別在最簡(jiǎn)單的地方翻車6.1 異或不是加法區(qū)分“無(wú)進(jìn)位和”與“數(shù)值和”我見(jiàn)過(guò)不少初學(xué)者以為異或就是“直接相加但不進(jìn)位”然后理所當(dāng)然地把所有加法換成異或。這通常在只需要判斷奇偶位或識(shí)別差異時(shí)有效但一旦你真正需要數(shù)值結(jié)果就會(huì)出錯(cuò)。5 ^ 3 等于6不是8因?yàn)楫惢騺G掉了全部進(jìn)位而 5 3 等于8。做算術(shù)邏輯、統(tǒng)計(jì)總數(shù)時(shí)絕對(duì)不能混用。一個(gè)判斷技巧是如果你關(guān)心的是“總共有多少”用加法如果你關(guān)心的是“哪些位不一樣”用異或。6.2 負(fù)數(shù)在補(bǔ)碼體系下的異或結(jié)果可能讓你意外不同編程語(yǔ)言里異或都是按二進(jìn)制的補(bǔ)碼表示逐位運(yùn)算的。拿 -1 ^ 1 來(lái)說(shuō)結(jié)果不是0而是 -2。因?yàn)樵谘a(bǔ)碼里-1 的所有位都是1與1異或后最低位變成0其余位保持1對(duì)應(yīng)補(bǔ)碼 -2。很多語(yǔ)言新手在這里第一次踩坑會(huì)覺(jué)得異或結(jié)果“不符合直覺(jué)”。如果要在跨語(yǔ)言項(xiàng)目里用位運(yùn)算處理負(fù)數(shù)務(wù)必先搞清楚目標(biāo)語(yǔ)言里整數(shù)的位寬和補(bǔ)碼規(guī)則。C/C 里溢出是未定義行為Java 和 Python 的處理方式又各有差異。我的習(xí)慣是預(yù)處理里先把負(fù)數(shù)轉(zhuǎn)成無(wú)符號(hào)形式或明確記錄符號(hào)位避免在負(fù)數(shù)位模式下推導(dǎo)半天。6.3 非整數(shù)數(shù)據(jù)不能直接按字節(jié)異或序列化是前置步驟有些同學(xué)會(huì)把字符串或浮點(diǎn)數(shù)直接拿去異或結(jié)果發(fā)現(xiàn)語(yǔ)言報(bào)錯(cuò)或行為詭異。原因很簡(jiǎn)單異或運(yùn)算定義在整數(shù)位模式上字符串、浮點(diǎn)數(shù)需要先序列化成字節(jié)序列再逐字節(jié)處理。比如在 Python 里我對(duì)一個(gè)字符串做異或加密會(huì)先 encode 成 bytes再對(duì)每個(gè)字節(jié)做運(yùn)算最后再 decode 回來(lái)。浮點(diǎn)數(shù)更麻煩它的字節(jié)表示和數(shù)值本身完全不是一回事直接異或字節(jié)得到的結(jié)果沒(méi)有數(shù)學(xué)意義。如果確實(shí)需要做校驗(yàn)應(yīng)該選擇把浮點(diǎn)轉(zhuǎn)成二進(jìn)制表示或字符串之后再校驗(yàn)。搞清楚對(duì)象的底層表示才能安全使用異或。6.4 性能與可讀性的平衡什么時(shí)候該用什么時(shí)候別用異或指令在 CPU 層面非常快一條指令就能完成比分支判斷通常更高效。但這不代表你要把代碼里所有邏輯都改寫成異或?，F(xiàn)代編譯器已經(jīng)會(huì)幫你優(yōu)化掉很多多余分支而寫滿異或的代碼一旦缺少注釋后來(lái)維護(hù)的人很可能要花很長(zhǎng)時(shí)間才能讀懂。我的判斷標(biāo)準(zhǔn)很簡(jiǎn)單如果異或能讓代碼意圖更清晰比如表示“翻轉(zhuǎn)狀態(tài)”“校驗(yàn)數(shù)據(jù)”“提取差異”就用如果只是為了顯得自己很懂位運(yùn)算把一個(gè)簡(jiǎn)單的累加邏輯改成異或那是給自己和同事挖坑。可讀性是工程代碼的第一屬性位運(yùn)算只是達(dá)成目的的工具。7. 踩過(guò)幾次坑之后我總結(jié)的異或使用清單說(shuō)了這么多最后整理一份我實(shí)際工作中沉淀下來(lái)的檢查清單。遇到位運(yùn)算場(chǎng)景時(shí)我會(huì)先過(guò)一遍這幾個(gè)問(wèn)題數(shù)據(jù)里是否存在“成對(duì)出現(xiàn)、期望抵消”的結(jié)構(gòu)如果是優(yōu)先考慮異或。我的目標(biāo)是“求差異”“翻轉(zhuǎn)狀態(tài)”“快速校驗(yàn)”還是“算術(shù)求和”只有前三者適合異或。參與運(yùn)算的數(shù)據(jù)是否都是整數(shù)或可序列化為字節(jié)負(fù)數(shù)、浮點(diǎn)、字符串要先做處理。代碼里用了異或旁邊有沒(méi)有注釋如果沒(méi)有至少保證變量名和函數(shù)名能讓人猜出意圖。在需要數(shù)據(jù)恢復(fù)的場(chǎng)景有沒(méi)有想清楚異或校驗(yàn)的邊界它無(wú)法檢測(cè)所有錯(cuò)誤組合。有一次我調(diào)試一個(gè)通信模塊數(shù)據(jù)偶爾出現(xiàn)丟失卻半天找不到原因。后來(lái)用十六進(jìn)制逐字節(jié)打印才意識(shí)到是校驗(yàn)位的算法寫反了把數(shù)據(jù)幀本身也異或進(jìn)了校驗(yàn)值。這類問(wèn)題如果不借助二進(jìn)制層面的觀察很容易在邏輯層面打轉(zhuǎn)。后來(lái)我每次做異或相關(guān)調(diào)試都會(huì)先用二進(jìn)制把輸入和輸出打印出來(lái)逐位對(duì)比通常很快就能定位。理解異或的最佳方式其實(shí)不是背那些公式和結(jié)論而是花一個(gè)下午親手在紙上把幾個(gè)數(shù)字展開(kāi)成二進(jìn)制一步步做按位運(yùn)算再在代碼里打斷點(diǎn)觀察每一步的結(jié)果。我當(dāng)年就是這樣把一個(gè)看似簡(jiǎn)單的運(yùn)算符徹底弄明白的。之后再看那些精巧的位運(yùn)算解法就不再覺(jué)得是奇技淫巧而是能找到清晰的推導(dǎo)路徑。希望這篇內(nèi)容也能幫你建立屬于自己的異或直覺(jué)。