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