聊一聊位掩碼（Bit Mask）
掩碼 (Mask) 是一種位運算技巧，它使用一個特定的值（掩碼）與目標值進行 $\mathtt{\&}$ (與)、$\mathtt{|}$ (或)、$\mathtt{\wedge}$ (異或) 運算，以精確地、批次地操作、提取或檢查目標值中的一個或多個位。
掩碼利用位運算的特性，透過設定掩碼中的特定位為 1 或 0，來控制目標值中對應位的行為。 具體來說，掩碼可以用來提取某些位的值，清除某些位的值，反轉某些位的值，或者設定某些位的值。
透過與運算（$\mathtt{\&}$）和一個掩碼，可以提取目標值中特定位置的位。例如，假設我們有一個 8 位的二進位制數 10101100，我們想提取其中的第 3 位（從右數起，0 開始計數）。我們可以使用掩碼 00000100：
1
2
3
4
10101100 (目標值)
& 00000100 (掩碼)
------------
00000100 (結果)
結果 00000100 表示第 3 位是 1。
這一技巧可以用來提取多位，比如想要提取某個數的低 4 位，可以使用掩碼 00001111。
透過與運算（$\mathtt{\&}$）和一個掩碼，可以清除目標值中特定位置的位。例如，假設我們有一個 8 位的二進位制數 10101100，我們想清除其中的第 3 位。我們可以使用掩碼 11111011：
1
2
3
4
10101100 (目標值)
& 11111011 (掩碼)
------------
10101000 (結果)
結果 10101000 表示第 3 位被清除為 0。
清除就是不提取某些位 lol
透過異或運算（$\mathtt{\wedge}$）和一個掩碼，可以反轉目標值中特定位置的位。例如，假設我們有一個 8 位的二進位制數 10101100，我們想反轉其中的第 3 位。我們可以使用掩碼 00000100：
1
2
3
4
10101100 (目標值)
^ 00000100 (掩碼)
------------
10101000 (結果)
結果 10101000 表示第 3 位被反轉。
透過或運算（$\mathtt{|}$）和一個掩碼，可以設定目標值中特定位置的位。例如，假設我們有一個 8 位的二進位制數 10101000，我們想設定其中的第 3 位為 1。我們可以使用掩碼 00000100：
1
2
3
4
10101000 (目標值)
| 00000100 (掩碼)
------------
10101100 (結果)
結果 10101100 表示第 3 位被設定為 1。
構造合適的掩碼是使用技巧的關鍵。
- 單個位: $\mathtt{1 \ll n}$
- $\mathtt{1 \ll 5}$ ($\mathtt{00100000}$) 是第 5 位的掩碼。
- 連續低位: $\mathtt{(1 \ll n) - 1}$
- $\mathtt{(1 \ll 8) - 1}$ ($\mathtt{0xFF}$) 是低 8 位的掩碼。
- 全 1 掩碼: $\mathtt{\sim 0}$ (即 $-1$)
- $\mathtt{0xFFFFFFFF}$ (假設 32 位)
- 全 0 掩碼: $\mathtt{0}$
在 CSAPP Data Lab 中，我們有一道題目要求用位運算實現三目運算子 x ? y : z。我們可以使用條件掩碼來實現這一點。
1
2
3
4
5
int conditional(int x, int y, int z) {
int mask = !!x;
mask = ~mask + 1;
return (y & mask) | (z & ~mask);
}
這段程式碼的邏輯是：
- 計算
mask = !!x，如果x非零，mask為1，否則為0。 - 透過
mask = ~mask + 1，將mask轉換為全 1 (0xFFFFFFFF) 或全 0 (0x0)。 - 返回
(y & mask) | (z & ~mask)，如果x非零，結果為y，否則為z。
掩碼是一種強大的位運算技巧，可以用來精確地操作和檢查資料中的特定位。
透過合理構造掩碼，我們可以高效地實現各種位操作，如提取、清除、反轉和設定位。在實際程式設計中，掌握掩碼的使用能夠幫助我們編寫出更高效、更簡潔的程式碼。