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