如果你刷過一陣子算法題大概率見過這道經(jīng)典題目一個(gè)整數(shù)數(shù)組里除了兩個(gè)數(shù)字只出現(xiàn)一次其他數(shù)字都出現(xiàn)了兩次要求找出這兩個(gè)只出現(xiàn)一次的數(shù)字。第一次看到這題的時(shí)候我其實(shí)挺不屑的心想這不就是哈希表一遍掃過去的事嗎直到某次面試對(duì)面讓我在白板上寫最優(yōu)解我寫了哈希表版本對(duì)面問了一句“能不能不用額外空間”我才意識(shí)到這道題的真正考點(diǎn)不在“找出來”而在你懂不懂位運(yùn)算。這道題的通用解法確實(shí)非常漂亮先用全員異或拿到兩個(gè)目標(biāo)數(shù)字的異或結(jié)果再?gòu)倪@個(gè)結(jié)果里挑出任意一個(gè)為 1 的二進(jìn)制位把數(shù)組分成兩組每組再做一次全員異或兩個(gè)目標(biāo)數(shù)字就分頭落網(wǎng)了。整個(gè)過程只需要 O(n) 時(shí)間和 O(1) 空間代碼不超過二十行。聽起來簡(jiǎn)單但里面每一個(gè)細(xì)節(jié)都藏著位運(yùn)算的核心功底比如為什么異或能抵消成對(duì)元素、為什么取最低位的 1 就能完成分組、為什么分組之后其他成對(duì)數(shù)字依然會(huì)被消掉。這篇文章我就以這道題為主線把位運(yùn)算的底層邏輯拆開揉碎講清楚。不光是給你 AC 代碼更重要的是把每一步的“為什么”講明白讓你下次遇到變種題也能自己推出來。適合剛接觸位運(yùn)算的初學(xué)者也適合想把這題徹底吃透再去面試的人。1. 題目還原與三種解法的演化路徑先把原題明確一下給定一個(gè)非空整數(shù)數(shù)組除了某兩個(gè)元素只出現(xiàn)一次以外其余每個(gè)元素均出現(xiàn)兩次。找出這兩個(gè)只出現(xiàn)一次的元素。要求時(shí)間復(fù)雜度 O(n)、空間復(fù)雜度 O(1)。很多平臺(tái)上的描述會(huì)強(qiáng)調(diào)“結(jié)果順序不限”這是為了方便判題不用糾結(jié)先輸出誰。我第一次做這題時(shí)第一反應(yīng)當(dāng)然是哈希表。遍歷數(shù)組把每個(gè)數(shù)字出現(xiàn)的次數(shù)記錄下來最后篩出次數(shù)為 1 的兩個(gè)數(shù)字。這個(gè)方案很直觀也絕對(duì)正確但空間復(fù)雜度是 O(n)。如果面試官只是考“會(huì)不會(huì)做”哈希表已經(jīng)足夠如果考“會(huì)不會(huì)最優(yōu)解”那就必須上位運(yùn)算。還有一種思路是用集合Set。遍歷數(shù)組時(shí)如果當(dāng)前數(shù)字已經(jīng)在集合里就刪掉否則加入。因?yàn)槌蓪?duì)出現(xiàn)的數(shù)字會(huì)先加入再刪除最終集合里剩下的就是那兩個(gè)只出現(xiàn)一次的數(shù)字。這個(gè)方案的平均時(shí)間復(fù)雜度也是 O(n)很多語言里 Set 底層是哈希表所以空間復(fù)雜度同樣是 O(n)。它的思路比字典更輕巧但依然沒有擺脫額外空間。位運(yùn)算解法則是完全不同的路子。它不借助任何容器只靠異或運(yùn)算的數(shù)學(xué)性質(zhì)就把兩個(gè)目標(biāo)數(shù)字從一堆成對(duì)數(shù)字里“過濾”出來。核心思想分三步第一全員異或把成對(duì)的數(shù)字全部消掉剩下兩個(gè)目標(biāo)數(shù)字的異或值第二從這個(gè)異或值里找一個(gè)為 1 的二進(jìn)制位這個(gè)位說明兩個(gè)目標(biāo)數(shù)字在該位上取值不同第三用這個(gè)位把原數(shù)組分成兩組兩個(gè)目標(biāo)數(shù)字必然分到不同組再對(duì)每組做全員異或就能分別拿到它們。這三個(gè)步驟每一步都值得展開講。接下來我就按這個(gè)順序把位運(yùn)算的底層機(jī)制一點(diǎn)點(diǎn)拆開。2. 異或運(yùn)算的“抵消魔法”成對(duì)元素的自動(dòng)過濾機(jī)制異或運(yùn)算的符號(hào)是^它的運(yùn)算規(guī)則是“相同為 0不同為 1”。在二進(jìn)制層面它的本質(zhì)是按位比較兩個(gè) bit 一樣就輸出 0不一樣就輸出 1。比如5 ^ 35 的二進(jìn)制是1013 的二進(jìn)制是011逐位異或得到110也就是 6。從這個(gè)規(guī)則能直接推出幾個(gè)重要性質(zhì)。第一a ^ 0 a任何數(shù)和 0 異或都等于它自己。第二a ^ a 0任何數(shù)和它自己異或都等于 0。第三異或滿足交換律和結(jié)合律也就是說a ^ b ^ c和a ^ c ^ b結(jié)果完全一樣括號(hào)怎么加都不影響最終結(jié)果。這三個(gè)性質(zhì)組合起來就構(gòu)成了位運(yùn)算解法最核心的“抵消魔法”。假設(shè)數(shù)組是[1, 2, 1, 3, 2, 5]我們從頭到尾做全員異或1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5因?yàn)榻粨Q律可以重排成1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 51 ^ 1 02 ^ 2 0所以式子變成0 ^ 0 ^ 3 ^ 5 3 ^ 5也就是說全員異或的結(jié)果跟數(shù)組中其他成對(duì)數(shù)字完全無關(guān)只等于兩個(gè)目標(biāo)數(shù)字的異或值。這就像把所有成對(duì)的物品放上秤互相抵消最后剩下的就是那兩個(gè)沒有配對(duì)的東西。這里有個(gè)容易忽略的細(xì)節(jié)為什么數(shù)組中其他數(shù)字一定成對(duì)出現(xiàn)不會(huì)出現(xiàn)三四個(gè)相同的數(shù)字因?yàn)轭}目條件里寫死了“其余每個(gè)元素均出現(xiàn)兩次”。如果題目改成“大部分出現(xiàn)兩次少數(shù)出現(xiàn)三次”那異或就不能直接消掉奇數(shù)次出現(xiàn)的數(shù)字了。所以審題要仔細(xì)位運(yùn)算解法的成立是建立在題目限制條件之上的。在實(shí)際面試中如果題目條件稍有變化位運(yùn)算的思路也要跟著調(diào)整這一點(diǎn)在后面的擴(kuò)展部分會(huì)專門講。理解了全員異或的作用之后你已經(jīng)邁出了關(guān)鍵一步。現(xiàn)在你手里有一個(gè)非常關(guān)鍵的值x ^ y。但這個(gè)值是兩個(gè)目標(biāo)數(shù)字的異或結(jié)果你沒法從3 ^ 5 6反推出3和5分別是多少。怎么辦下一步就是從這個(gè)異或值里找線索把那兩個(gè)數(shù)字分開。3. 從 x xor y 里定位差異位選對(duì)分組依據(jù)x ^ y的結(jié)果里每一個(gè)為 1 的 bit 都意味著什么回到異或的定義兩個(gè) bit 不同則結(jié)果為 1。所以異或結(jié)果中某個(gè) bit 為 1就說明x和y在這一位上一個(gè)是 0 另一個(gè)是 1。換句話說這個(gè) bit 就是x和y之間的一個(gè)“差異標(biāo)記”。反過來如果x ^ y的某個(gè) bit 是 0說明x和y在這一位上相同可能是都為 0也可能都為 1。這樣的 bit 對(duì)我們區(qū)分兩個(gè)目標(biāo)數(shù)字毫無幫助。所以要分組我們必須找一個(gè)x和y不一樣的位也就是在x ^ y中為 1 的位。拿前面的例子繼續(xù)算3 ^ 5 66 的二進(jìn)制是110。注意這里有個(gè)容易掉的坑3的二進(jìn)制是0115的二進(jìn)制是101如果只寫三位的話3 ^ 5 110 6沒問題。但實(shí)際在計(jì)算機(jī)里整數(shù)通常用 32 位存儲(chǔ)最高位前面全是 0。這些高位 0 異或出來還是 0不影響結(jié)果但在做位運(yùn)算時(shí)腦子里要把符號(hào)位和補(bǔ)碼的規(guī)則想清楚尤其是負(fù)數(shù)的時(shí)候后面會(huì)單獨(dú)講。回到 6 的二進(jìn)制110從低到高看第 0 位是 0說明 3 和 5 的最低位相同第 1 位是 1說明它們?cè)诘诙徊煌? 的第二位是 1 而 5 的第二位是 0第 2 位是 1說明它們?cè)诘谌灰膊煌? 的第三位是 0 而 5 的第三位是 1。所以我們可以選第 1 位也可以選第 2 位作為分組依據(jù)。那具體選哪一個(gè)位呢最經(jīng)典的寫法是取“最低位的 1”也就是lowbit x ^ y -(x ^ y)。這個(gè)式子很多初學(xué)者第一次看到會(huì)懵其實(shí)它利用了補(bǔ)碼的一個(gè)特殊性質(zhì)一個(gè)數(shù)的負(fù)數(shù)在二進(jìn)制表示里等于它的反碼加一。x (-x)的結(jié)果恰好能提取出 x 的最低位 1 所在的位置其余位全部變 0。舉例說明x 12二進(jìn)制是1100。-x在補(bǔ)碼表示下是0100假設(shè)只寫四位實(shí)際是 32 位里有符號(hào)數(shù)的補(bǔ)碼。12 (-12)等于1100 0100 0100也就是 4正好是 12 的最低位的 1 所在的位置。這個(gè)技巧在樹狀數(shù)組Fenwick Tree里也經(jīng)常用是位運(yùn)算里的一個(gè)經(jīng)典小工具?；氐轿覀兊膱?chǎng)景x ^ y 6二進(jìn)制110。6 (-6)6 的補(bǔ)碼負(fù)數(shù)二進(jìn)制表示中最低位的 1 也在第 1 位所以6 (-6) 2對(duì)應(yīng)二進(jìn)制010。這個(gè) 2 就表示“第 1 位是分組依據(jù)”。有些讀者可能會(huì)問為什么一定用最低位的 1用其他位置的 1 行不行答案是完全行。只要這個(gè)位在x ^ y中是 1就能把兩個(gè)目標(biāo)數(shù)字分到不同組。選最低位的 1 只是工程上最方便、最不容易出錯(cuò)的寫法因?yàn)樗恍枰恍写ax -x就能算出來。如果你想選一個(gè)更高的位可以用循環(huán)從低位往高位找或者用一些內(nèi)置函數(shù)如__builtin_ctz等但那樣代碼會(huì)更長(zhǎng)。面試時(shí)我建議直接用x (-x)簡(jiǎn)潔又好解釋。還有一個(gè)必須講的細(xì)節(jié)為什么分組依據(jù)確定之后數(shù)組里的成對(duì)數(shù)字不會(huì)“搗亂”假設(shè)我們選擇第 k 位作為分組標(biāo)準(zhǔn)把數(shù)組中所有第 k 位為 1 的數(shù)字分到 A 組第 k 位為 0 的數(shù)字分到 B 組。那么對(duì)于任意一個(gè)出現(xiàn)了兩次的數(shù)字z它在第 k 位上的值當(dāng)然是固定的要么是 0 要么是 1所以它的兩次出現(xiàn)一定會(huì)被分到同一個(gè)組里。然后在組內(nèi)做全員異或時(shí)這兩個(gè)相同的z就會(huì)相互抵消就像它們?cè)谠瓟?shù)組里做全員異或時(shí)一樣。換句話說分組的操作不會(huì)破壞成對(duì)元素的抵消特性它只把不同組的數(shù)字隔離開讓兩個(gè)目標(biāo)數(shù)字分別成為各自組里唯一“落單”的元素。4. 分組后的全員異或兩個(gè)目標(biāo)數(shù)字如何分頭落網(wǎng)一旦分組依據(jù)確定剩下的操作就機(jī)械而清晰了。拿到lowbit之后再次遍歷整個(gè)數(shù)組對(duì)每個(gè)數(shù)字num判斷num lowbit是否為 0如果為 0說明num在分組位上取 0歸入 B 組如果不為 0說明取 1歸入 A 組。A 組和 B 組各自做全員異或最終得到的兩個(gè)值就是x和y。這里要注意一個(gè)細(xì)節(jié)num lowbit的結(jié)果不是非 0 即 1而可能是 lowbit 本身或者更大的值所以判斷條件寫(num lowbit) 0還是(num lowbit) ! 0才能正確區(qū)分不要寫成(num lowbit) 1這是初學(xué)位運(yùn)算時(shí)最容易犯的錯(cuò)誤。因?yàn)閘owbit是 2 的冪num lowbit的結(jié)果要么是 0要么就是lowbit這個(gè)值本身永遠(yuǎn)不可能是 1除非lowbit就是 1。這個(gè)細(xì)節(jié)如果寫錯(cuò)了測(cè)試用例很容易暴露問題。整個(gè)算法的代碼可以寫成這樣我用最經(jīng)典的寫法def singleNumber(nums): xorsum 0 for num in nums: xorsum ^ num lowbit xorsum (-xorsum) a 0 b 0 for num in nums: if num lowbit: a ^ num else: b ^ num return [a, b]同樣的事情用 Java 寫也是一樣的邏輯public int[] singleNumber(int[] nums) { int xorsum 0; for (int num : nums) { xorsum ^ num; } int lowbit xorsum (-xorsum); int a 0, b 0; for (int num : nums) { if ((num lowbit) 0) { a ^ num; } else { b ^ num; } } return new int[]{a, b}; }以nums [1, 2, 1, 3, 2, 5]為例跑一遍完整流程全員異或1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 6。取 lowbit6 (-6) 2。按第二位分組1的二進(jìn)制是0011 2 0進(jìn) B 組。2的二進(jìn)制是0102 2 2進(jìn) A 組。1再次出現(xiàn)還是進(jìn) B 組。3的二進(jìn)制是0113 2 2進(jìn) A 組。2再次出現(xiàn)還是進(jìn) A 組。5的二進(jìn)制是1015 2 0進(jìn) B 組。A 組異或2 ^ 3 ^ 2 3。B 組異或1 ^ 1 ^ 5 5。返回[3, 5]正好是兩個(gè)只出現(xiàn)一次的數(shù)字。算法的時(shí)空復(fù)雜度其實(shí)非常清晰兩次線性遍歷時(shí)間是 O(n)額外變量只有幾個(gè)整數(shù)空間是 O(1)。這也是這道題能拿滿分的原因。寫到這里我忍不住想提醒一個(gè)很多人容易踩的坑如果你在某個(gè)在線判題平臺(tái)上提交平臺(tái)要求返回的數(shù)組里兩個(gè)數(shù)字的順序不限那沒問題。但如果面試官說“請(qǐng)按升序輸出”你就需要在返回前做個(gè)比較把小的放前面。這個(gè)不是算法層面的難點(diǎn)但實(shí)際寫代碼時(shí)容易漏掉導(dǎo)致面試表現(xiàn)打折扣。5. 代碼邊界檢查與位運(yùn)算易錯(cuò)點(diǎn)排查代碼只有十幾行但邊界情況和易錯(cuò)點(diǎn)其實(shí)不少。我把實(shí)際刷題和面試過程中踩過的坑、還有很多人常犯的錯(cuò)誤集中列出來你在自己寫的時(shí)候可以對(duì)著檢查。第一個(gè)坑是“只有一個(gè)元素只出現(xiàn)一次”的數(shù)組。題目明確說了有兩個(gè)只出現(xiàn)一次的元素所以數(shù)組長(zhǎng)度至少為 2。但如果你拿到一個(gè)長(zhǎng)度只有 2 且兩個(gè)元素不同的數(shù)組比如[1, 2]全員異或等于3lowbit 等于1按最低位分組1 進(jìn) B2 進(jìn) A返回[2, 1]依然正確。所以算法在長(zhǎng)度較小的合法輸入下也能工作。第二個(gè)坑是負(fù)數(shù)。位運(yùn)算在負(fù)數(shù)上的表現(xiàn)跟正數(shù)不同因?yàn)樨?fù)整數(shù)在計(jì)算機(jī)里用補(bǔ)碼表示取反加一之后最高位符號(hào)位參與運(yùn)算。x (-x)這個(gè)技巧對(duì)負(fù)數(shù)依然成立因?yàn)檠a(bǔ)碼的設(shè)計(jì)目的就是讓加減法在二進(jìn)制層面統(tǒng)一運(yùn)算。比如x -6它的補(bǔ)碼在很多位上都是 1x (-x)依然能提取出最低位的 1。所以算法處理負(fù)數(shù)是沒問題的但如果你用打印二進(jìn)制的方式來驗(yàn)證可能會(huì)被一堆 1 嚇到心里要有數(shù)。第三個(gè)坑是比較分組條件時(shí)寫錯(cuò)判斷式。前面已經(jīng)講過num lowbit的結(jié)果要么是 0 要么是lowbit本身所以判斷(num lowbit) 1是邏輯錯(cuò)誤。還有一個(gè)變體有人會(huì)寫(num lowbit) 0這是對(duì)的因?yàn)閘owbit是正數(shù)非 0 即代表num在該位為 1。第四個(gè)坑是取lowbit的兩種寫法的理解差異。除了x (-x)也有人寫x (~x 1)這是因?yàn)?x在補(bǔ)碼上正好等于~x 1兩種寫法完全等價(jià)。千萬不要寫x (~x)那會(huì)得到 0因?yàn)橐粋€(gè)數(shù)和它的反碼按位與每一位都相反結(jié)果全是 0。第五個(gè)坑是數(shù)組里存在 0 的情況。0 和任何數(shù)異或都等于那個(gè)數(shù)本身所以 0 不會(huì)影響全員異或的結(jié)果。但是分組時(shí) 0 在任意位上都是 0它只會(huì)進(jìn)入 B 組對(duì)結(jié)果也沒有影響。只要目標(biāo)數(shù)字不是 0 且數(shù)組中 0 是成對(duì)出現(xiàn)的算法一樣正確。如果目標(biāo)數(shù)字本身就是 0題目通常會(huì)允許因?yàn)椤爸怀霈F(xiàn)一次”也包括 0此時(shí)全員異或結(jié)果就是另一個(gè)數(shù)lowbit 也能正常計(jì)算算法依然成立。還有一個(gè)很有意思的思維實(shí)驗(yàn)為什么全員異或完得到的結(jié)果x ^ y一定不為 0因?yàn)槿绻?0說明x y但題目說這兩個(gè)數(shù)字是不同的。所以x ^ y至少有一個(gè) bit 是為 1 的。這也保證了lowbit一定存在不可能出現(xiàn)找不到分組依據(jù)的情況。這個(gè)邏輯鏈條可以用反證法來講給面試官聽會(huì)顯得你思路很清晰。6. 變種題與工程場(chǎng)景中的位運(yùn)算延伸思考這道題的思路不止能解這一道題。面試官特別喜歡在“只出現(xiàn)一次的數(shù)字”系列上做文章最常見的就是第二題和第三題也就是其他數(shù)字都出現(xiàn)三次只有一個(gè)出現(xiàn)一次或者有兩個(gè)出現(xiàn)一次但你得從三個(gè)里區(qū)分。這些變種雖然都叫“只出現(xiàn)一次的數(shù)字”但解法思路完全不同。先說說“其他數(shù)字出現(xiàn)三次只有一個(gè)出現(xiàn)一次”的情況。全員異或在這里幫不上忙因?yàn)槿齻€(gè)相同的數(shù)字異或的結(jié)果是它自己而不是 0抵消不了。正確思路是統(tǒng)計(jì)每一位上 1 的出現(xiàn)次數(shù)然后對(duì) 3 取余。因?yàn)槠渌麛?shù)字都出現(xiàn)三次它們的貢獻(xiàn)在每一位上都能被 3 整除剩下的余數(shù)就是那個(gè)只出現(xiàn)一次的數(shù)字在這一位上的值。這個(gè)解法需要按 32 位逐位統(tǒng)計(jì)時(shí)間和空間都很固定屬于位運(yùn)算的另一種典型應(yīng)用用按位計(jì)數(shù)來找出“不按套路出牌”的元素。我曾經(jīng)在一次模擬面試中把這道變種講給一個(gè)同學(xué)聽他聽完感嘆說原來位運(yùn)算不只是異或還能當(dāng)計(jì)數(shù)器用。再說一個(gè)變種如果把題目改成“有兩個(gè)數(shù)字出現(xiàn)一次其他數(shù)字出現(xiàn)兩次但要求兩個(gè)數(shù)字必須按升序輸出”你需要做的只是在返回前加上排序判斷算法主體不變。工程里會(huì)不會(huì)用到這種位運(yùn)算技巧說實(shí)話工作中直接寫這種代碼的頻率不高但位運(yùn)算的思維無處不在。比如在處理權(quán)限系統(tǒng)時(shí)一個(gè)整數(shù)的不同 bit 可以代表不同的權(quán)限位判斷用戶是否有某個(gè)權(quán)限就是檢查某一位是否為 1設(shè)置權(quán)限就是按位或、取消權(quán)限就是按位與取反。做網(wǎng)絡(luò)協(xié)議解析時(shí)一個(gè)字節(jié)的高 4 位和低 4 位可能分別代表不同的字段提取字段就得用移位和掩碼。再比如做 Bloom Filter 時(shí)多個(gè)哈希函數(shù)要對(duì)同一個(gè) bitmap 做置位操作底層也是位運(yùn)算。所以別看題目花哨背后的“用 bit 表示狀態(tài)”“用掩碼隔離信息”的思想在真實(shí)項(xiàng)目里非常常見。還有一類比較偏的面試題會(huì)考察lowbit的變體應(yīng)用。比如統(tǒng)計(jì)一個(gè)整數(shù)二進(jìn)制里有多少個(gè) 1經(jīng)典做法就是不斷用x (x - 1)消掉最低位的 1每消一次計(jì)數(shù)加一。這個(gè)寫法的原理跟x (-x)剛好互補(bǔ)一個(gè)是提取最低位的 1一個(gè)是直接消掉最低位的 1。掌握這兩個(gè)技巧很多二進(jìn)制計(jì)數(shù)的題目都能迎刃而解?；氐竭@道“只出現(xiàn)一次的數(shù)字 III”如果你想在牛客或力扣上把位運(yùn)算的功力再往上提一個(gè)臺(tái)階我建議你做三件事。第一把本題的哈希表解法和位運(yùn)算解法都寫一遍對(duì)比兩種寫法的速度差異在數(shù)據(jù)規(guī)模大的測(cè)試下位運(yùn)算的速度優(yōu)勢(shì)會(huì)非常明顯。第二把“出現(xiàn)三次”的變種題也實(shí)現(xiàn)一遍然后思考如果題目變成“其他數(shù)字都出現(xiàn)四次有兩個(gè)數(shù)字出現(xiàn)一次”該怎么處理這個(gè)思考過程比記答案重要得多。第三試著用位運(yùn)算去解一些看起來毫不相關(guān)的題目比如判斷一個(gè)數(shù)是不是 2 的冪n 0 (n (n - 1)) 0或者在沒有臨時(shí)變量的情況下交換兩個(gè)整數(shù)a ^ b; b ^ a; a ^ b這些都是在鍛煉你對(duì)二進(jìn)制本質(zhì)的理解。我現(xiàn)在回頭看這道題它最打動(dòng)人的地方不是那個(gè)精妙的 lowbit 技巧而是一種思維方式當(dāng)常規(guī)的“統(tǒng)計(jì)”手法碰到空間限制的時(shí)候能不能換一個(gè)角度從數(shù)的本質(zhì)屬性——二進(jìn)制表示——出發(fā)把“是否相同”變成“異或?yàn)?0”把“是否不同”變成“某個(gè)位上的 1”。這種從表象到本質(zhì)的切換正是位運(yùn)算的魅力所在。引申開去很多看似需要額外空間的問題只要你能從數(shù)據(jù)本身的二進(jìn)制特征入手都有可能被簡(jiǎn)化為常數(shù)空間的解法。這也是為什么很多面試官明知道候選人能答出哈希表方案還是堅(jiān)持追問一路問到位運(yùn)算的原因。