1. 問題引入從“機器人塔”到狀態(tài)壓縮幾年前我在準(zhǔn)備算法競賽時遇到了藍橋杯國賽的一道經(jīng)典題目——“機器人塔”。這道題初看像是一個模擬或者搜索題但如果你真的去嘗試用DFS或BFS去枚舉每一層機器人的擺放很快就會陷入指數(shù)級的狀態(tài)爆炸。題目描述大致是給定兩種機器人假設(shè)為A和B它們按照某種規(guī)則堆疊成塔。規(guī)則通常是上層的機器人種類由下層的兩個相鄰機器人決定比如下層兩個相同則上層為A不同則為B或者反之。已知塔的層數(shù)和底層或頂層的某種狀態(tài)求可能的底層排列總數(shù)。我第一次看到這題直覺就是暴力枚舉底層。假設(shè)底層有N個機器人每個位置有A/B兩種可能那么狀態(tài)總數(shù)就是2^N。對于N20這就是百萬級別似乎還能接受但別忘了我們還需要根據(jù)規(guī)則逐層向上推導(dǎo)驗證整個塔的構(gòu)造是否符合要求比如總機器人數(shù)量限制。這個驗證過程本身是O(N^2)的。這樣一來總復(fù)雜度就是O(2^N * N^2)當(dāng)N稍大比如30計算量立刻變得不可接受。這就是“機器人塔”問題的核心矛盾狀態(tài)空間巨大但規(guī)則具有極強的局部性和確定性。正是在這種場景下位運算和狀態(tài)壓縮技術(shù)從后臺走向了前臺成為破解問題的利器。它不僅僅是“快一點”而是將問題的規(guī)模從“不可計算”變?yōu)椤翱捎嬎恪睆摹澳M”變?yōu)椤坝成洹薄＝裉煳覀兙蛠韽氐撞鸾膺@道題看看如何將一層機器人的排列壓縮成一個整數(shù)又如何通過位操作在O(1)的時間復(fù)雜度內(nèi)完成一整層狀態(tài)的推導(dǎo)。2. 核心邏輯拆解規(guī)則、狀態(tài)與遞推在深入位運算的魔法之前我們必須先吃透題目最本質(zhì)的邏輯。任何技巧都是為邏輯服務(wù)的邏輯不清技巧再高也是空中樓閣。2.1 規(guī)則的形式化定義“機器人塔”問題的規(guī)則萬變不離其宗下一層的狀態(tài)完全由上一層相鄰的兩個元素決定。我們通常用0和1來代表兩種機器人比如A0 B1。最常見的規(guī)則有兩種異或XOR規(guī)則如果下層兩個機器人相同同為0或同為1則它們上方的機器人為0如果不同則為1。這恰好是**按位異或^**運算上層位 左下層位 ^ 右下層位。同或XNOR規(guī)則與異或相反。如果下層兩個相同則上層為1不同則為0。這可以通過上層位 ~(左下層位 ^ 右下層位)或1 ^ (左下層位 ^ 右下層位)來實現(xiàn)。我們以經(jīng)典的“異或規(guī)則”為例進行后續(xù)講解。這個規(guī)則有一個美妙的性質(zhì)它構(gòu)成了一個“異或金字塔”。如果我們把底層狀態(tài)寫成一個二進制數(shù)那么整個塔的構(gòu)建過程就變成了這個二進制數(shù)不斷進行“收縮”異或的過程。2.2 狀態(tài)壓縮將一層映射為一個整數(shù)狀態(tài)壓縮的核心思想是用一個整數(shù)的二進制位來表示一個有限集合的狀態(tài)。在“機器人塔”中一層有N個位置每個位置有0/1兩種狀態(tài)。那么這一層的所有可能狀態(tài)就可以用一個N位的二進制數(shù)來唯一表示。例如底層有5個位置狀態(tài)為[A, B, A, A, B] 對應(yīng)[0, 1, 0, 0, 1]。我們可以將其看作一個二進制數(shù)01001。但是注意在數(shù)組中索引0通常在最左邊而在二進制數(shù)中最低位LSB在最右邊。為了編程方便我們通常約定數(shù)組的第i個元素從左到右對應(yīng)整數(shù)的第i位從低到高或從高到低需統(tǒng)一。我個人更習(xí)慣讓數(shù)組索引0對應(yīng)二進制最低位即最右邊這樣右移操作更直觀。但也可以反過來只要在整個計算過程中保持一致即可。假設(shè)我們采用“索引i對應(yīng)二進制從低到高第i位”那么狀態(tài)[0,1,0,0,1]對應(yīng)的整數(shù)就是(10)*? (11)*? ...更直觀的方法是state 0;for i from 0 to N-1: if (layer[i] 1) state | (1 i);這樣[0,1,0,0,1]得到 state (11) | (14) 2 16 18 (二進制10010)。注意此時二進制表示10010從左到右高位到低位對應(yīng)的是數(shù)組從右到左索引4到0。這需要一點時間來適應(yīng)。關(guān)鍵點在于一旦我們將一層壓縮成一個整數(shù)state那么這一層的全部信息都包含在了這個int或long long里。對層的操作就變成了對整數(shù)的位操作。2.3 遞推關(guān)系如何從一層得到上一層這是位運算技巧最閃耀的部分。給定第k層的狀態(tài)state_k一個N位的二進制數(shù)我們?nèi)绾慰焖偾蟪龅趉-1層的狀態(tài)state_{k-1}一個N-1位的二進制數(shù)根據(jù)異或規(guī)則state_{k-1}的第j位 state_k的第j位 ^state_k的第j1位。如果用整數(shù)和位運算來表達呢我們可以這樣思考我們需要將state_k和它自身左移一位后的結(jié)果進行按位異或。但要注意邊界state_k的最高位第N-1位在運算時需要與一個“虛擬的”第N位進行異或而這一位是不存在的。實際上state_{k-1}只有 N-1 位它的最高位由state_k的第 N-2 位和第 N-1 位異或得到。因此遞推公式為state_{k-1} (state_k ^ (state_k 1)) ((1 (N-1)) - 1)讓我們分解一下state_k 1將state_k右移一位。這樣原來第j1位的值現(xiàn)在就移到了第j位。state_k ^ (state_k 1)現(xiàn)在state_k的第j位原值與(state_k1)的第j位原第j1位進行異或恰好得到了state_{k-1}的第j位的結(jié)果。但是這個結(jié)果目前仍然是一個N位的數(shù)因為state_k是N位其最高位第N-1位是state_k的第N-1位與0因為右移移入0的異或這個值是無效的。 ((1 (N-1)) - 1)這個操作被稱為“掩碼Mask操作”。(1 (N-1)) - 1會生成一個低N-1位全為1更高位全為0的掩碼。通過按位與操作我們將上一步結(jié)果中無效的最高位及更高位清零只保留低N-1位這正是我們想要的state_{k-1}。這個過程的時間復(fù)雜度是O(1)一次異或、一次移位、一次與操作。相比于傳統(tǒng)的循環(huán)O(N)計算上一層這是巨大的效率提升。當(dāng)我們需要從底層一直推導(dǎo)到塔頂或反之時這個優(yōu)勢會被層層放大。3. 算法設(shè)計與實現(xiàn)枚舉、驗證與優(yōu)化掌握了核心的位運算遞推后我們就可以設(shè)計完整的算法了。算法的骨架通常是枚舉所有可能的底層狀態(tài)對每一個狀態(tài)快速推導(dǎo)整個塔并驗證是否符合題目要求。3.1 基礎(chǔ)算法框架假設(shè)題目給定塔有R層底層寬度為W需要滿足塔中A類機器人和B類機器人的總數(shù)分別為X和Y。枚舉底層狀態(tài)底層狀態(tài)是一個W位的二進制數(shù)。我們用一個整數(shù)bottom從0枚舉到(1 W) - 1。這枚舉了所有2^W種可能。構(gòu)建全塔并計數(shù)對于每個bottom我們需要知道整個塔所有機器人的0/1數(shù)量。方法A正向推導(dǎo)從bottom開始不斷用公式layer (layer ^ (layer 1)) mask向上推導(dǎo)直到層數(shù)變?yōu)?。在推導(dǎo)每一層時我們需要統(tǒng)計該層中1的個數(shù)即B機器人的數(shù)量。0的個數(shù)可以通過當(dāng)前層寬度 - 1的個數(shù)得到。方法B逆向思維有時題目給定的是頂層狀態(tài)和總層數(shù)要求底層。這時就需要從頂層向下推導(dǎo)遞推公式會略有不同下層狀態(tài)是上層狀態(tài)和上層狀態(tài)左移一位的某種組合但可能不唯一需要搜索。驗證與統(tǒng)計在構(gòu)建過程中累加A和B的總數(shù)。最后與題目要求的X,Y進行比較。如果匹配則此bottom是一個合法解計數(shù)器加一。關(guān)鍵優(yōu)化快速統(tǒng)計二進制中1的個數(shù)在循環(huán)中我們需要頻繁計算一個整數(shù)x的二進制表示中1的個數(shù)也稱為 popcount。自己寫循環(huán)while(x) {cnt; x x-1;}固然可以但在這種密集計算中使用編譯器內(nèi)置函數(shù)是更優(yōu)選擇__builtin_popcount(x)適用于int。__builtin_popcountll(x)適用于long long。 這些函數(shù)通常使用CPU的特殊指令實現(xiàn)速度極快。3.2 實現(xiàn)示例與代碼剖析下面是一個針對“已知底層寬度W和層數(shù)R統(tǒng)計所有可能底層狀態(tài)”問題的核心代碼框架假設(shè)規(guī)則為異或且只需計數(shù)。#include iostream using namespace std; int main() { int R, W; // R層底層寬度W // 假設(shè)題目要求統(tǒng)計所有可能的底層數(shù)這里簡化為例 cin R W; long long total_count 0; int bottom_mask (1 W) - 1; // 底層狀態(tài)的掩碼 for (int bottom 0; bottom bottom_mask; bottom) { int current_layer bottom; int current_width W; int total_ones __builtin_popcount(bottom); // 統(tǒng)計底層1的個數(shù) for (int level 1; level R; level) { // 從底層向上建R-1層 current_width--; // 上一層寬度減1 int layer_mask (1 current_width) - 1; // 當(dāng)前層的掩碼 // 核心遞推計算上一層狀態(tài) current_layer (current_layer ^ (current_layer 1)) layer_mask; // 統(tǒng)計當(dāng)前層1的個數(shù) total_ones __builtin_popcount(current_layer); } // 這里可以添加驗證條件例如總機器人個數(shù)等 // if (total_ones target_B total_zeros target_A) ... // 本例中我們只是演示流程假設(shè)所有塔都合法 total_count; } cout total_count endl; return 0; }這段代碼的潛在問題與優(yōu)化枚舉范圍2^W是巨大的。即使W20也有百萬級循環(huán)內(nèi)部還有R層最多20層的循環(huán)整體復(fù)雜度O(2^W * R)。對于W30直接枚舉是不可能的。剪枝很多bottom狀態(tài)在推導(dǎo)到中間層時可能就已經(jīng)違反了某些約束比如某一層的1的個數(shù)已經(jīng)超過了剩余層可能的最大值。這時可以提前終止進行剪枝。對稱性對于異或規(guī)則塔的狀態(tài)可能具有對稱性。例如bottom和~bottom mask按位取反構(gòu)建的塔其0/1總數(shù)可能是互補的?？梢岳眠@一點減少一半的枚舉量但需小心規(guī)則是否完全對稱。3.3 進階優(yōu)化記憶化搜索與DP當(dāng)直接枚舉不可行時W較大我們必須尋找更聰明的方法。注意到題目往往只關(guān)心總數(shù)X和Y而不關(guān)心具體形態(tài)。這提示我們可以用動態(tài)規(guī)劃DP。我們可以定義狀態(tài)dp[level][width][countA][countB]表示構(gòu)建到第level層、該層寬度為width、且已經(jīng)使用了countA個A和countB個B的方案數(shù)。但這樣的狀態(tài)空間仍然很大。一個更巧妙的DP是基于最后兩層狀態(tài)的轉(zhuǎn)移。因為下一層只由上一層決定我們可以定義dp[level][state][countA]表示當(dāng)前在第level層該層狀態(tài)為state且從塔頂?shù)奖緦永塾嬍褂昧薱ountA個A的方案數(shù)。然后從頂層向底層或反之轉(zhuǎn)移。轉(zhuǎn)移時我們需要知道對于給定的上層狀態(tài)state_u寬度w有多少種可能的下層狀態(tài)state_d寬度w1能生成它。這需要解一個線性方程組state_u的每一位state_u[j] state_d[j] ^ state_d[j1]。對于異或這等價于state_d[j1] state_d[j] ^ state_u[j]。這意味著只要我確定了state_d的第一個位最左邊或最右邊整個state_d就唯一確定了。因此對于每個state_u最多只有2種可能的state_d對應(yīng)第一個位是0或1。這樣DP的轉(zhuǎn)移代價就是常數(shù)級的。通過這種DP我們可以將復(fù)雜度從O(2^W)降低到O(R * W * 2^W)甚至更好結(jié)合滾動數(shù)組和狀態(tài)壓縮可以處理更大的W。這才是解決此類問題的“標(biāo)準(zhǔn)”競賽思路位運算遞推是其中的關(guān)鍵計算單元。4. 避坑指南與實戰(zhàn)心得理論很美好但一寫代碼就出錯。下面是我在實現(xiàn)“機器人塔”及相關(guān)位運算問題中踩過的坑以及總結(jié)出的經(jīng)驗。4.1 位運算的優(yōu)先級陷阱這是最經(jīng)典的錯誤來源。位運算符,|,^,,的優(yōu)先級低于比較運算符,!更低于算術(shù)運算符,-,*,/。錯誤示例if (state mask target) // 錯誤 優(yōu)先級高于 這實際上被解釋為if (state (mask target))幾乎永遠(yuǎn)不是你想要的。正確做法勤加括號。if ((state mask) target)在寫復(fù)雜的位運算表達式時即使你知道優(yōu)先級也建議用括號明確意圖提高代碼可讀性避免深夜調(diào)試的噩夢。4.2 移位操作的邊界與符號移位位數(shù)超過類型寬度在C/C中如果右操作數(shù)移位位數(shù)大于等于左操作數(shù)類型的位寬行為是未定義的。對于int a; a 32或a 33假設(shè)int是32位結(jié)果不可預(yù)測。應(yīng)對在構(gòu)造掩碼時如(1 W) - 1確保W小于類型的位寬對于int應(yīng)小于32。對于更大的W使用long long位寬通常為64。有符號整數(shù)的右移對于有符號整數(shù)如int是算術(shù)右移還是邏輯右移由實現(xiàn)定義。大多數(shù)編譯器對有符號數(shù)進行算術(shù)右移高位補符號位。這可能導(dǎo)致意想不到的結(jié)果特別是當(dāng)你把狀態(tài)當(dāng)作無符號位圖使用時。應(yīng)對在處理位掩碼時統(tǒng)一使用無符號類型如unsigned int,unsigned long long。它們的右移是邏輯右移高位補0行為是確定的。將上述代碼中的int改為unsigned int是更好的實踐。4.3 掩碼計算的細(xì)節(jié)掩碼(1 n) - 1用于獲取低n位為1的數(shù)。這里有兩個坑當(dāng)n等于類型位寬時1 32對于32位整數(shù)是未定義行為。如果你需要取全部低位可以直接用~0u無符號整數(shù)-1或者(unsigned int)-1。中間結(jié)果溢出(1 30) - 1是安全的。但如果你要計算(1LL 60) - 1確保使用long long字面量1LL。一個更安全的掩碼計算習(xí)慣是unsigned int mask (W sizeof(unsigned int)*8) ? ~0u : ((1u W) - 1);4.4 狀態(tài)與索引的對應(yīng)關(guān)系混亂如前所述數(shù)組索引與二進制位的對應(yīng)關(guān)系必須從頭到尾保持一致。我推薦兩種清晰的方法方法一索引i對應(yīng)從低到高第i位LSB為索引0優(yōu)點(state i) 1可以直接取第i位的值設(shè)置第i位為1用state | (1u i)。右移操作與層遞推中的state 1物理意義匹配最右邊的元素參與生成其左上的元素這里需要根據(jù)你的遞推公式物理意義再確認(rèn)。缺點二進制表示看起來是反的。方法二索引i對應(yīng)從高到低第i位MSB為索引0優(yōu)點二進制表示與數(shù)組順序一致直觀。缺點取位和設(shè)位操作稍麻煩可能需要(state (W-1-i)) 1。我的建議選擇一種在草稿紙上畫出一個簡單例子比如3層塔完整走一遍遞推過程確保你的遞推公式、掩碼計算、位提取都在同一個約定下工作。并在代碼開頭用注釋明確說明你的約定。4.5 性能瓶頸與優(yōu)化取舍在競賽中即使使用了位運算枚舉2^W也可能太慢。此時需要判斷W到底有多大如果W202^20 ≈ 1e6配合O(R)的驗證通?？梢栽?秒內(nèi)完成。如果W24約1600萬狀態(tài)就需要非常高效的代碼和可能的剪枝。剪枝是否有效提前計算每一層可能的最小/最大1的個數(shù)在遞推過程中如果累計值已經(jīng)超出范圍立即跳出。是否必須枚舉所有底層題目可能只要求輸出一個解或方案數(shù)模某個值?？紤]DP或數(shù)學(xué)方法。使用對稱性如果問題關(guān)于0和1對稱只需枚舉一半狀態(tài)最后結(jié)果乘2注意全0和全1可能重復(fù)計算的情況。位運算是指數(shù)級算法的加速器但它不能改變指數(shù)級算法的本質(zhì)。當(dāng)W超過25時一定要考慮DP、搜索剪枝或數(shù)學(xué)規(guī)律而不是硬枚舉。5. 舉一反三位運算在算法競賽中的其他妙用“機器人塔”是位運算應(yīng)用的典范但絕非孤例。掌握這種思維你能在眾多場景中化繁為簡。子集枚舉對于一個有n個元素的集合其所有子集可以用一個0到(1n)-1的整數(shù)表示。i的二進制位表示第i個元素是否在子集中。遍歷所有子集for(int mask0; mask(1n); mask)。遍歷某個集合mask的所有非空子集也有經(jīng)典循環(huán)for(int submask; sub; sub(sub-1)mask)。這在狀態(tài)壓縮DP中無處不在。狀態(tài)壓縮DP如旅行商問題TSP用整數(shù)mask表示已經(jīng)訪問過的城市集合。dp[mask][i]表示從起點出發(fā)訪問了mask集合中的城市最后停在城市i的最短路徑。狀態(tài)轉(zhuǎn)移時檢查mask中哪些位是1表示哪些城市已訪問哪些是0?？焖倥袛嗥媾肌⑷∧ 1等價于x % 2用于判斷奇偶速度快得多。x 3等價于x % 4。lowbit 與樹狀數(shù)組lowbit(x) x -x可以取出x二進制表示中最低位的1及其后面的0。這是樹狀數(shù)組Fenwick Tree的核心操作用于高效維護前綴和。集合交并補操作用位表示集合后交集a b并集a | b差集a (~b)對稱差a ^ b檢查子集(a b) a這些操作都是O(1)的。棋盤/網(wǎng)格類問題比如“八皇后”的變種用三個整數(shù)col, diag1, diag2分別表示列、主對角線、副對角線是否被占用。放置皇后時只需檢查相應(yīng)的位是否為0放置后通過|操作設(shè)置位?；氐健皺C器人塔”它訓(xùn)練的正是一種“狀態(tài)壓縮”和“位操作模擬”的復(fù)合能力。當(dāng)你再遇到類似“每一行狀態(tài)只與上一行有關(guān)”、“每個位置只有少數(shù)幾種狀態(tài)”的題目時第一時間就應(yīng)該想到能不能用一個整數(shù)表示一行/一個狀態(tài)能不能用位運算O(1)地完成狀態(tài)轉(zhuǎn)移這道題的價值遠(yuǎn)不止于解出它本身。它像一把鑰匙打開了一類高效算法設(shè)計的大門。我在后來遇到許多看似復(fù)雜的搜索、DP問題都是靠這種“壓縮狀態(tài)位運算轉(zhuǎn)移”的思路找到了突破口。編程競賽中時間和空間都是奢侈品而位運算往往是能將這兩者同時節(jié)省下來的寶貴工具。理解它熟練它在關(guān)鍵時刻它就能為你創(chuàng)造出那一點至關(guān)重要的優(yōu)勢。