聊一聊位掩碼（Bit Mask）

掩碼 (Mask) 是一種位運算技巧，它使用一個特定的值（掩碼）與目標值進行 $\mathtt{\&}$ (與)、$\mathtt{|}$ (或)、$\mathtt{\wedge}$ (異或) 運算，以精確地、批次地操作、提取或檢查目標值中的一個或多個位。

基本概念

掩碼利用位運算的特性，透過設定掩碼中的特定位為 1 或 0，來控制目標值中對應位的行為。 具體來說，掩碼可以用來提取某些位的值，清除某些位的值，反轉某些位的值，或者設定某些位的值。

提取位

透過與運算（$\mathtt{\&}$）和一個掩碼，可以提取目標值中特定位置的位。例如，假設我們有一個 8 位的二進位制數 10101100，我們想提取其中的第 3 位（從右數起，0 開始計數）。我們可以使用掩碼 00000100：

  10101100  (目標值)
& 00000100  (掩碼)
------------
  00000100  (結果)

結果 00000100 表示第 3 位是 1。

這一技巧可以用來提取多位，比如想要提取某個數的低 4 位，可以使用掩碼 00001111。

清除位

透過與運算（$\mathtt{\&}$）和一個掩碼，可以清除目標值中特定位置的位。例如，假設我們有一個 8 位的二進位制數 10101100，我們想清除其中的第 3 位。我們可以使用掩碼 11111011：

  10101100  (目標值)
& 11111011  (掩碼)
------------
  10101000  (結果)

結果 10101000 表示第 3 位被清除為 0。

清除就是不提取某些位 lol

反轉位

透過異或運算（$\mathtt{\wedge}$）和一個掩碼，可以反轉目標值中特定位置的位。例如，假設我們有一個 8 位的二進位制數 10101100，我們想反轉其中的第 3 位。我們可以使用掩碼 00000100：

  10101100  (目標值)
^ 00000100  (掩碼)
------------
  10101000  (結果)

結果 10101000 表示第 3 位被反轉。

設定位

透過或運算（$\mathtt{|}$）和一個掩碼，可以設定目標值中特定位置的位。例如，假設我們有一個 8 位的二進位制數 10101000，我們想設定其中的第 3 位為 1。我們可以使用掩碼 00000100：

  10101000  (目標值)
| 00000100  (掩碼)
------------
  10101100  (結果)

結果 10101100 表示第 3 位被設定為 1。

構造掩碼

構造合適的掩碼是使用技巧的關鍵。

1. 單個位: $\mathtt{1 \ll n}$
   1. $\mathtt{1 \ll 5}$ ($\mathtt{00100000}$) 是第 5 位的掩碼。
2. 連續低位: $\mathtt{(1 \ll n) - 1}$
   1. $\mathtt{(1 \ll 8) - 1}$ ($\mathtt{0xFF}$) 是低 8 位的掩碼。
3. 全 1 掩碼: $\mathtt{\sim 0}$ (即 $-1$)
   1. $\mathtt{0xFFFFFFFF}$ (假設 32 位)
4. 全 0 掩碼: $\mathtt{0}$

條件掩碼

在 CSAPP Data Lab 中，我們有一道題目要求用位運算實現三目運算子 x ? y : z。我們可以使用條件掩碼來實現這一點。

int conditional(int x, int y, int z) {
  int mask = !!x;          // mask 為 1 如果 x 非零，否則為 0
  mask = ~mask + 1;       // mask 為 0xFFFFFFFF 如果 x 非零，否則為 0x0
  return (y & mask) | (z & ~mask);
}

這段程式碼的邏輯是：

1. 計算 mask = !!x，如果 x 非零，mask 為 1，否則為 0。
2. 透過 mask = ~mask + 1，將 mask 轉換為全 1 (0xFFFFFFFF) 或全 0 (0x0)。
3. 返回 (y & mask) | (z & ~mask)，如果 x 非零，結果為 y，否則為 z。

總結

掩碼是一種強大的位運算技巧，可以用來精確地操作和檢查資料中的特定位。

透過合理構造掩碼，我們可以高效地實現各種位操作，如提取、清除、反轉和設定位。在實際程式設計中，掌握掩碼的使用能夠幫助我們編寫出更高效、更簡潔的程式碼。