Bitmask 位运算

### Bitmask 位运算

#### 1. 概述

Bitmask（位掩码）是一种利用整数的二进制表示来高效存储和操作小规模布尔集合（Boolean set）的技术。在 C/C++/Java 等语言中，整数以二进制位序列存储，因此可以通过位运算直接操作这些位，相比 `vector<bool>`、`bitset` 或 `set<int>` 等结构，位运算的效率更高，尤其适用于竞赛编程中的集合操作。

#### 2. 基本表示

* **存储方式** ：使用 32 位或 64 位有符号整数（如 `int` 或 `long long`）表示最多 32 或 64 个元素的集合。例如，32 位整数的每一位对应集合中的一个元素（0 表示未选中，1 表示选中）。
* **索引规则** ：采用  **0-based indexing** （从右向左编号，最右侧为第 0 位）。例如，整数 `S = 34`（十进制）的二进制为 `100010`，对应集合 `{1, 5}`（第 1 位和第 5 位为 1）。

#### 3. 核心位运算操作

##### 3.1 乘除 2 的快速运算

通过 **左移（`<<`）** 和 **右移（`>>`）** 实现：

* **左移 `k` 位** ：`S << k` 等价于 `S × 2^k`（补 0）。
* **右移 `k` 位** ：`S >> k` 等价于 `S ÷ 2^k`（向下取整，丢弃最低位）。

**示例** （以 `S = 34` 为例）：

```text
S = 34 (100010) → S << 1 = 68 (1000100)  // ×2
S = 34 (100010) → S >> 1 = 17 (10001)   // ÷2（向下取整）
```

##### 3.2 设置第 `j` 位（Set）

使用 **按位或（`|=`）** 操作：

```text
S |= (1 << j)
```

**原理** ：将 `1` 左移 `j` 位（生成仅第 `j` 位为 1 的掩码），再与原数 `S` 按位或，强制第 `j` 位为 1。

**示例** （`S = 34`，设置第 3 位）：

```text
S = 34 (100010) → 1 << 3 = 8 (001000)
S |= 8 → S = 42 (101010)
```

##### 3.3 检查第 `j` 位（Check）

使用 **按位与（`&`）** 操作：

```text
T = S & (1 << j)
```

* 若 `T = 0`，第 `j` 位为 0（未选中）；
* 若 `T ≠ 0`（实际为 `1 << j`），第 `j` 位为 1（选中）。

**示例** （`S = 42`）：

* 检查第 3 位：`42 & (1 << 3) = 42 & 8 = 8 ≠ 0` → 第 3 位为 1。
* 检查第 2 位：`42 & (1 << 2) = 42 & 4 = 0` → 第 2 位为 0。

##### 3.4 清除第 `j` 位（Clear）

使用 **按位与（`&=`）** 和  **按位取反（`~`）** ：

```text
S &= ~(1 << j)
```

**原理** ：`~(1 << j)` 生成仅第 `j` 位为 0 的掩码，再与 `S` 按位与，强制第 `j` 位为 0。

**示例** （`S = 42`，清除第 1 位）：

```text
S = 42 (101010) → ~(1 << 1) = 111111...1111101 (32 位补码)
S &= ~2 → S = 40 (101000)
```

##### 3.5 翻转第 `j` 位（Toggle）

使用  **按位异或（`^=`）** ：

```text
S ^= (1 << j)
```

**原理** ：异或操作会翻转第 `j` 位（1→0，0→1）。

**示例** （`S = 40`）：

* 翻转第 2 位：`40 ^ (1 << 2) = 40 ^ 4 = 44 (101100)`。
* 翻转第 3 位：`40 ^ (1 << 3) = 40 ^ 8 = 32 (100000)`。

##### 3.6 获取最低位的 1（LSB）

使用公式：

```text
T = S & (-S)
```

**原理** ：`-S` 是 `S` 的补码（二进制取反 + 1），与 `S` 按位与后，仅保留最低位的 1。

**示例** （`S = 40`）：

```text
S = 40 (000...101000) → -S = 111...011000 (补码)
S & (-S) = 8 (000...001000) → 最低位 1 在第 3 位。
```

##### 3.7 初始化全 1 集合

生成包含 `n` 个元素的全 1 集合（`n ≤ 32`）：

```text
S = (1 << n) - 1
```

**原理** ：`1 << n` 生成 `100...0`（共 `n+1` 位），减 1 后变为 `111...1`（共 `n` 个 1）。

**示例** ：

* `n = 3`：`(1 << 3) - 1 = 8 - 1 = 7 (111)`。
* `n = 5`：`(1 << 5) - 1 = 32 - 1 = 31 (11111)`。

#### 4. 注意事项

* **溢出风险** ：当 `n > 32` 时，32 位整数可能溢出，需使用 64 位整数（如 `long long`）。
* **索引范围** ：确保 `j` 在 `0` 到 `31`（或 `63`）之间，避免越界。
* **补码表示** ：负数以补码存储，需注意右移操作的符号扩展（无符号数右移补 0，有符号数可能补符号位）。

#### 5. 总结

Bitmask 通过位运算实现了集合操作的高效性，核心操作包括：

| 操作            | 代码                 | 说明                      |
| :---------------- | :--------------------- | :-------------------------- |
| 设置第 `j` 位 | `S                   | = (1 << j)`               |
| 检查第 `j` 位 | `S & (1 << j)`   | 返回非 0 表示选中         |
| 清除第 `j` 位 | `S &= ~(1 << j)` | 强制第 `j` 位为 0       |
| 翻转第 `j` 位 | `S ^= (1 << j)`  | 1→0，0→1                |
| 获取最低位 1    | `S & (-S)`       | 提取最低位的 1            |
| 全 1 集合       | `(1 << n) - 1`   | 初始化 `n` 个元素的集合 |

掌握这些操作后，可高效处理集合的并、交、差等运算，是竞赛编程中的重要技巧。