聊一聊位掩码（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。

总结

掩码是一种强大的位运算技巧，可以用来精确地操作和检查数据中的特定位。

通过合理构造掩码，我们可以高效地实现各种位操作，如提取、清除、反转和设置位。在实际编程中，掌握掩码的使用能够帮助我们编写出更高效、更简洁的代码。