---
title: 通过位运算快速生成所有的子序列
createTime: 2026/01/09 16:15:00
cover: /images/elysia/10.jpg
coverStyle:
    layout: right
permalink: /archives/ea20bdda-0d49-4472-a647-2e305a930d11/
---
## 一、子序列的本质

子序列是从原字符串中选择任意数量的字符（可以是 0 个、1 个、...、所有字符），且保持这些字符的原始顺序形成的字符串。

例如：原字符串 `"abc"` 的子序列包括 `"a"`, `"b"`, `"c"`, `"ab"`, `"ac"`, `"bc"`, `"abc"` 和空字符串 `""`（共 $2^3 = 8$ 种可能性）。

## 二、位掩码（Bitmask）的引入

假设字符串长度为 `n`，我们可以用一个 `n` 位的二进制数来表示是否选择某个字符：
- 二进制数的每一位对应原字符串的一个字符。
- 如果某一位是 `1`，表示选择对应的字符；如果是 `0`，表示不选择。

例如，对于字符串 `"abc"`（`n=3`）：

| 二进制数 | 十进制 | 选择情况 | 生成子序列 |
| :--- | :--- | :--- | :--- |
| `101` | 5 | 选择第 1 个字符 "a" 和第 3 个字符 "c" | `"ac"` |
| `010` | 2 | 选择第 2 个字符 "b" | `"b"` |

## 三、遍历所有可能的二进制数

所有可能的二进制数范围是 `0`（全 0）到 $2^n - 1$（全 1）。例如，`n=3` 时：
- 范围是 `000` (0) 到 `111` (7)，共 $2^3 = 8$ 种可能。
- 每个二进制数对应一种子序列选择方式。
- 如果包含 `000` (0)，对应空字符串 `""`。若不需要空字符串，可以从 `1` 开始遍历。

## 四、如何将二进制数转换为子序列？

### 1. 外层循环：遍历所有可能的二进制数
对于 `n=3`，遍历 `1` (`001`) 到 `7` (`111`)。

### 2. 内层循环：检查每一位是否为 1
- 对于每个二进制数 `mask`，遍历其每一位 `i`（从 `0` 到 `n-1`）。
- 如果 `mask` 的第 `i` 位是 `1`（即 `mask & (1 << i)` 为真），则将原字符串的第 `i` 个字符加入子序列。

## 五、代码示例

```python
def get_all_subsequences(s):
    n = len(s)
    subsequences = []
    # 遍历 1 到 2^n - 1 (排除空字符串)
    for mask in range(1, 1 << n):
        subseq = []
        for i in range(n):
            # 检查 mask 的第 i 位是否为 1
            if mask & (1 << i):
                subseq.append(s[i])
        subsequences.append(''.join(subseq))
    return subsequences

# 测试
print(get_all_subsequences("abc"))
# 输出: ['a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
```

## 六、应用场景

在处理类似 **X 质数** 的问题时，我们需要检查一个数字的所有数字子序列。通过这种位运算的方式，可以非常高效地生成所有组合并进行判断。

```python
def solve_x_prime(num):
    s = str(num)
    n = len(s)
    for mask in range(1, 1 << n):
        subseq_str = ""
        for i in range(n):
            if mask & (1 << i):
                subseq_str += s[i]
        
        # 将生成的子序列转换为整数并判断是否为质数
        p = int(subseq_str)
        if is_prime(p):
            return True
    return False
```