聊一聊位掩碼（Bit Mask）

發表於 分類於 閱讀次數： Waline： 文章字數： 1.5k

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

基本概念

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

提取位

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

1
2
3
4
  10101100  (目標值)
& 00000100  (掩碼)
------------
  00000100  (結果)

結果 00000100 表示第 3 位是 1。

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

清除位

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

1
2
3
4
  10101100  (目標值)
& 11111011  (掩碼)
------------
  10101000  (結果)

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

清除就是不提取某些位 lol

反轉位

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

1
2
3
4
  10101100  (目標值)
^ 00000100  (掩碼)
------------
  10101000  (結果)

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

設定位

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

1
2
3
4
  10101000  (目標值)
| 00000100  (掩碼)
------------
  10101100  (結果)

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

構造掩碼

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

  1. 單個位: 1 ≪ n
    1. 1 ≪ 5 (00100000) 是第 5 位的掩碼。
  2. 連續低位: (1 ≪ n) − 1
    1. (1 ≪ 8) − 1 (0xFF) 是低 8 位的掩碼。
  3. 全 1 掩碼:  ∼ 0 (即 −1)
    1. 0xFFFFFFFF (假設 32 位)
  4. 全 0 掩碼: 0

條件掩碼

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

1
2
3
4
5
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。

總結

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

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