# 3.3 高阶位运算

---

## 一、这一节要学什么？

在上一节里，我们已经会了最基础的按位与、按位或、按位异或、取反、左移、右移。接下来要进入真正“能拿来做题”的部分。

这一节的重点不是再背几个符号，而是学会把位运算当成一套工具箱来使用。你会看到：

- 怎么只改某一位、不动别的位；
- 怎么一次性提取一段二进制位；
- 怎么快速找到“最低位的 1”；
- 怎么在 $O(1)$ 时间判断一个数是不是 2 的幂；
- 怎么用异或找“只出现一次”的数；
- 怎么把“选或不选”压成一个整数，枚举所有方案。

如果说 3.2 还是“认识工具”，那 3.3 更像是“学会用工具解题”。

---

## 二、先介绍 `unsigned`

这一节我们主要讨论“非负整数”的位运算，所以在 C++ 里，优先推荐使用 `unsigned` 类型。

原因很简单：

- 它本来就不表示负数；
- 做位运算时，不容易被“符号位”干扰；
- 像右移这样的操作，课堂里更容易讲清楚。

### 1. `unsigned int` 是什么

```cpp
unsigned int x;
```

它表示无符号整数，也就是只能存 $0$ 和正整数，不能存负数。

在大多数 OJ 和常见编译环境里：

- `int` 通常是 32 位；
- `unsigned int` 也通常是 32 位。

区别在于：

- `int` 要留一部分范围给负数；
- `unsigned int` 把全部 32 位都拿来表示非负数。

所以常见范围可以记成：

- `int`：大约 $-2^{31}$ 到 $2^{31}-1$；
- `unsigned int`：$0$ 到 $2^{32}-1$。

如果课堂里讨论的是“32 位二进制串”，那么 `unsigned int` 非常合适。

### 2. `unsigned long long` 是什么

```cpp
unsigned long long x;
```

它也是无符号整数，只是位数更大。常见环境里，它通常是 64 位。

所以常见范围可以记成：

- `unsigned long long`：$0$ 到 $2^{64}-1$。

它适合下面这些场景：

- 位数可能超过 32 位；
- 要写 `1 << k`，而 `k` 可能比较大；
- 需要把更长的二进制状态装进一个整数。

例如：

```cpp
unsigned long long x = 1ull << 40;
```

这里如果你写成 `1 << 40`，就很危险，因为 `1` 默认是 `int`，位宽不够。写成 `1ull` 才表示“这是一个 64 位无符号整数 1”。

### 3. 什么时候用哪一个？

- 只讨论 32 位以内的普通位运算题：优先用 `unsigned int`。
- 可能涉及更高位，或者要安全地写较大的移位：优先用 `unsigned long long`。

课堂里可以先把这条经验记住：

> 32 位用 `unsigned int`，64 位用 `unsigned long long`。

### 4. 输入和输出怎么写

#### `unsigned int`

```cpp
unsigned int x;
cin >> x;
cout << x << '\n';
```

#### `unsigned long long`

```cpp
unsigned long long x;
cin >> x;
cout << x << '\n';
```

和普通整数一样直接输入输出就可以。

### 5. 为什么这一节更推荐 `unsigned`

例如下面这个式子：

```cpp
x >> 1
```

如果 `x` 是无符号数，我们就可以直接把它理解成“所有二进制位整体右移一格，左边补 0”。

如果 `x` 是有符号数，右移时很多语言还会涉及“符号扩展”，课堂理解会麻烦得多。

所以这一节讨论位运算技巧时，默认主要站在 `unsigned` 的角度来讲。

### 6. 顺便提一句 `bitset`

虽然这一节主线不用 `bitset`，但你以后看题解或写调试代码时，还是会经常见到它。

最常见的用法是：

```cpp
#include <bitset>
#include <iostream>
using namespace std;

int main() {
    bitset<8> bs(13);      // 把十进制 13 转成 8 位二进制 00001101
    cout << bs << '\n';   // 直接输出整串二进制
    cout << bs.count() << '\n';  // 统计二进制里有几个 1
    cout << bs[0] << '\n';       // 读取最低位
    return 0;
}
```

它比较适合做这些事：

- 把一个整数的二进制形式直接打印出来；
- 快速观察某几位的变化；
- 写一些“看位”的小工具。

但是它也有很明显的缺陷，所以这节不把它当主角：

- 长度必须在编译时写死，不像数组或 `vector` 那样灵活；
- 像 `x & (-x)`、`x & (x - 1)`、`x + 1`、`x - 1` 这类高阶技巧，本质上还是整数运算更直接；
- 若频繁在 `bitset` 和整数之间来回转换，代码会更绕；
- `bs[0]` 是最低位，但输出时最高位在左，初学者很容易看反。

所以可以把它理解成一句话：

> `bitset` 适合“展示二进制”，不太适合替代这一节里的核心整数技巧。

---

## 三、先建立一个核心概念：掩码 mask

高阶位运算里最常见的词就是“掩码”。

你可以把掩码理解成一张“筛子”：

- 掩码某一位是 1，表示这一位要参与操作；
- 掩码某一位是 0，表示这一位尽量保持不动，或者被过滤掉。

例如，设

```text
x    = 11010110
mask = 00001111
```

那么：

```text
x & mask = 00000110   // 只保留末 4 位
x | mask = 11011111   // 末 4 位全部变成 1
x ^ mask = 11011001   // 末 4 位全部翻转
x & ~mask = 11010000  // 末 4 位全部清零
```

所以，许多位运算题本质上都在做两件事：

1. 先构造出一个合适的掩码。
2. 再用 `&`、`|`、`^`、`~` 去操作它。

这一节后面几乎所有公式，都可以看成是“掩码 + 位运算”的组合。

---

## 四、最常用的 4 个单点操作

下面默认：

- 右起最低位编号为第 0 位；
- 第 $k$ 位指的是右起第 $k$ 位；
- 用 `unsigned int x` 表示一个 32 位状态。

设 `x` 是原数，那么：

### 1. 把第 k 位变成 1

```cpp
x |= (1u << k);
```

原因：`1u << k` 只有第 $k$ 位是 1，和 `x` 按位或以后，第 $k$ 位一定变成 1，其余位不受影响。

### 2. 把第 k 位变成 0

```cpp
x &= ~(1u << k);
```

原因：`1u << k` 只有第 $k$ 位是 1，取反后只有第 $k$ 位是 0。再和 `x` 按位与，第 $k$ 位就会被清成 0，其余位保持不变。

### 3. 把第 k 位翻转

```cpp
x ^= (1u << k);
```

原因：异或 1 会翻转，异或 0 保持不变。

### 4. 读取第 k 位是 0 还是 1

```cpp
unsigned int bit = (x >> k) & 1u;
```

先把第 $k$ 位移到最低位，再和 1 相与，只保留这一位。

### 演示

设：

```text
x = 00101101
```

若 `k = 3`，那么第 3 位原本是 1。

```text
1u << 3        = 00001000
x | (1u << 3)  = 00101101   // 本来就是 1，不变
x & ~(1u << 3) = 00100101   // 第 3 位清零
x ^ (1u << 3)  = 00100101   // 第 3 位翻转
(x >> 3) & 1   = 1
```

### 对应程序 1：单点位编辑器

下面程序支持 4 类操作：设置某位、清零某位、翻转某位、查询某位。

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned int x;
    int q;
    cin >> x >> q;  // 读入初始状态和操作次数

    while (q--) {
        string op;
        int k;
        cin >> op >> k;  // 读入操作名和位编号

        if (op == "SET") {
            x |= (1u << k);  // 把第 k 位设为 1
        } else if (op == "CLEAR") {
            x &= ~(1u << k);  // 把第 k 位清成 0
        } else if (op == "FLIP") {
            x ^= (1u << k);  // 把第 k 位翻转
        } else if (op == "TEST") {
            cout << ((x >> k) & 1u) << '\n';  // 输出第 k 位当前是 0 还是 1
        }
    }

    cout << x << '\n';  // 输出最终状态的十进制值
    return 0;
}
```

---

## 五、连续区间上的位操作

真正的题目里，很多时候不是只改 1 位，而是要改“连续一段”。这时就要学会构造“连续若干个 1”的掩码。

### 1. 保留末 k 位

```cpp
x & ((1u << k) - 1)
```

因为：

```text
1u << k      = 1000...000   （1 后面 k 个 0）
(1u << k)-1  = 0111...111   （低 k 位全是 1）
```

例如：

```text
x = 11010110
k = 4
(1u << 4) - 1 = 00001111
x & 00001111  = 00000110
```

### 2. 把末 k 位全部清零

```cpp
x & ~((1u << k) - 1)
```

例如：

```text
x = 11010110
mask = 00001111
~mask = 11110000
x & ~mask = 11010000
```

### 3. 取出第 l 到第 r 位这段二进制

假设 $0 \le l \le r$，并且位编号仍然从右往左、从 0 开始。

公式：

```cpp
(x >> l) & ((1u << (r - l + 1)) - 1)
```

思路是两步：

1. 先把第 $l$ 位移到最低位。
2. 再保留低 $(r-l+1)$ 位。

例如：

```text
x = 11010110
取第 2 到第 5 位

x >> 2 = 00110101
保留低 4 位 = 00000101
```

所以第 2 到第 5 位组成的数是 `0101`，即十进制 5。

### 竖式感受 1：为什么“右移再与掩码”能取出一段位

还是以 `x = 11010110`，取第 2 到第 5 位为例：

```text
x           = 1 1 0 1 0 1 1 0
x >> 2      = 0 0 1 1 0 1 0 1
mask        = 0 0 0 0 1 1 1 1
------------------------
结果        = 0 0 0 0 0 1 0 1
```

从右往左看，原来第 2 到第 5 位的内容是 `0101`，右移后它被搬到了最低 4 位，再与上 `1111`，其他位就被全部滤掉了。

### 4. 用 y 替换 x 的第 l 到第 r 位

公式：

```cpp
unsigned int updateBits(unsigned int x, unsigned int y, int l, int r) {
    unsigned int mask = (1u << (r - l + 1)) - 1;
    x &= ~(mask << l);            // 先清空这一段
    x |= ((y & mask) << l);       // 再把 y 的低若干位填进去
    return x;
}
```

例如：

```text
x = 10000000000
y = 10101
l = 2, r = 6
```

替换后得到：

```text
10001010100
```

这正是“更新二进制位”这类题的标准做法。

### 竖式感受 2：区间替换到底做了哪两步

设 `x = 11101101`，把第 1 到第 3 位替换成 `y = 010`。

```text
x           = 1 1 1 0 1 1 0 1
mask        = 0 0 0 0 1 1 1 0
clear x     = 1 1 1 0 0 0 0 1
y << 1      = 0 0 0 0 0 1 0 0
------------------------
结果        = 1 1 1 0 0 1 0 1
```

你可以把“区间替换”理解成两个连续动作：

1. 先把目标区间擦干净；
2. 再把新内容平移到对应位置后填进去。

### 对应程序 2：区间取位与区间替换

```cpp
#include <bits/stdc++.h>
using namespace std;

unsigned int extractBits(unsigned int x, int l, int r) {
    unsigned int mask = (1u << (r - l + 1)) - 1;  // 低 len 位全是 1
    return (x >> l) & mask;  // 先右移，再保留低位
}

unsigned int updateBits(unsigned int x, unsigned int y, int l, int r) {
    unsigned int mask = (1u << (r - l + 1)) - 1;  // 先得到这一段的基础掩码
    x &= ~(mask << l);  // 把 x 的 [l, r] 区间清零
    x |= ((y & mask) << l);  // 把 y 的低若干位平移后填进去
    return x;  // 返回替换后的结果
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned int x, y;
    int l, r;
    cin >> x >> y >> l >> r;  // 读入原数、新数和区间端点

    cout << extractBits(x, l, r) << '\n';  // 输出取出的这一段
    cout << updateBits(x, y, l, r) << '\n';  // 输出区间替换后的结果
    return 0;
}
```

> 说明：上面程序默认 `r - l + 1 < 32`。如果可能用到更高位，建议把 `1u` 改成 `1ull`，并把类型换成 `unsigned long long`。

---

## 六、`x & (-x)`：只保留最低位的 1

这是位运算里最经典的高阶技巧之一，也常被叫做 `lowbit(x)`。

公式：

```cpp
x & (-x)
```

它的作用是：

> 只保留 `x` 二进制中最右边的那个 1，其余位全部清零。

### 例子 1

```text
x = 44 = 101100
x & (-x) = 000100 = 4
```

说明最低位的 1 在第 2 位，它的权值是 4。

### 例子 2

```text
x = 72 = 1001000
x & (-x) = 0001000 = 8
```

### 竖式感受：`x & (-x)` 为什么只剩一个 1

以 8 位下 `x = 44` 为例：

```text
x        = 0 0 1 0 1 1 0 0
~x       = 1 1 0 1 0 0 1 1
~x + 1   = 1 1 0 1 0 1 0 0   （这就是 -x 的补码）
------------------------
x & (-x) = 0 0 0 0 0 1 0 0
```

最右边那个 1 被单独保留下来，其余位都在按位与时被消掉了。

### 为什么成立？

设一个数的二进制长成这样：

```text
x = ?????1000...000
```

也就是：

- 最低位的 1 左边是什么无所谓；
- 最低位的 1 右边全是 0。

那么它的相反数 `-x` 在补码里，会恰好保留这一位对应的权值，和 `x` 相与以后，就只剩下这一个 1。

你不必每次都重新推补码，记住结论即可：

```cpp
unsigned int lowbit = x & -x;
```

在这里把 `x` 看成无符号整数，重点理解“二进制位模式”就够了。

### `lowbit` 有什么用？

- 找最低位的 1；
- 判断某个数能被多少个 2 连续整除；
- 树状数组里跳步；
- 把一个状态拆成若干个单独的二进制位。

---

## 七、`x & (x - 1)`：消掉最低位的 1

公式：

```cpp
x & (x - 1)
```

它的作用是：

> 把 `x` 最低位的那个 1 清掉，其他更高位尽量保持不变。

### 为什么成立？

设：

```text
x     = ?????1000...000
x - 1 = ?????0111...111
```

那么：

```text
x & (x - 1) = ?????0000...000
```

也就是说，最低位的 1 被清掉了。

### 例子

```text
x = 90 = 1011010

第一次：1011010 & 1011001 = 1011000 = 88
第二次：1011000 & 1010111 = 1010000 = 80
第三次：1010000 & 1001111 = 1000000 = 64
第四次：1000000 & 0111111 = 0000000 = 0
```

共做了 4 次才变成 0，所以 90 的二进制里有 4 个 1。

### 竖式感受：`x - 1` 会先改掉哪些位

以 8 位下 `x = 90 = 01011010` 为例：

```text
x         = 0 1 0 1 1 0 1 0
x - 1     = 0 1 0 1 1 0 0 1
------------------------
x & (x - 1) = 0 1 0 1 1 0 0 0
```

从右往左看，最低位那个 1 被清掉了，而它右边发生变化的部分在按位与后也全部消失，于是只剩“去掉最低位 1”后的结果。

### 用它统计 1 的个数

```cpp
int popcount(unsigned int x) {
    int cnt = 0;
    while (x) {
        x &= (x - 1);  // 每次清掉一个最低位的 1
        ++cnt;  // 记录一共清掉了多少次
    }
    return cnt;
}
```

循环几次，就有几个 1。

### 用它判断 2 的幂

如果一个正整数是 2 的幂，那么它的二进制里恰好只有一个 1。

所以：

```cpp
x > 0 && (x & (x - 1)) == 0
```

成立，当且仅当 `x` 是 2 的幂。

例如：

- `8 = 1000`，`8 & 7 = 0`，所以是 2 的幂；
- `12 = 1100`，`12 & 11 = 8`，不是 0，所以不是 2 的幂。

### 对应程序 3：`lowbit`、统计 1 的个数、判断 2 的幂

```cpp
#include <bits/stdc++.h>
using namespace std;

unsigned int lowbit(unsigned int x) {
    return x & (~x + 1u);  // 只保留最低位的 1
}

int popcount(unsigned int x) {
    int cnt = 0;
    while (x) {
        x &= (x - 1);  // 每次消掉一个最低位的 1
        ++cnt;  // 消掉几次，就说明原来有几个 1
    }
    return cnt;
}

bool isPowerOfTwo(unsigned int x) {
    return x > 0 && (x & (x - 1)) == 0;  // 正数且只含一个 1
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned int x;
    cin >> x;  // 读入一个非负整数

    cout << lowbit(x) << '\n';  // 输出最低位 1 的权值
    cout << popcount(x) << '\n';  // 输出二进制中 1 的个数
    cout << (isPowerOfTwo(x) ? "YES" : "NO") << '\n';  // 输出是否为 2 的幂
    return 0;
}
```

这里有两个细节值得注意：

- `lowbit(x)` 和 `x & (-x)` 是同一个意思；
- 统计 1 的个数时，循环次数正好等于 1 的个数。

---

## 八、右边连续的 1 和连续的 0

很多位运算题，专门喜欢考“最右边连续的一段”。下面这些式子都很常见。

### 1. `x & (x + 1)`：把右边连续的 1 清零

例如：

```text
x      = 10101111
x + 1  = 10110000
结果    = 10100000
```

也就是最右边那一串连续的 1 全没了。

### 竖式感受 1：`x & (x + 1)` 和 `x | (x + 1)`

以 `x = 10101111` 为例：

```text
x         = 1 0 1 0 1 1 1 1
x + 1     = 1 0 1 1 0 0 0 0
------------------------
x & (x + 1) = 1 0 1 0 0 0 0 0
x | (x + 1) = 1 0 1 1 1 1 1 1
```

所以：

- `x & (x + 1)` 会把最右边连续的 1 全清掉；
- `x | (x + 1)` 会把右起第一个 0 变成 1。

### 2. `x | (x + 1)`：把右起第一个 0 变成 1

例如：

```text
x      = 10101111
x + 1  = 10110000
结果    = 10111111
```

右起第一个 0 被点亮了，而它右边那一串 1 本来就是 1。

### 3. `x | (x - 1)`：把右边连续的 0 变成 1

例如：

```text
x      = 10110000
x - 1  = 10101111
结果    = 10111111
```

于是最右边那一串 0 全被填成 1。

### 4. `~x & (x + 1)`：取出最低位的 0

例如：

```text
x      = 10101111
~x     = 01010000
x + 1  = 10110000
结果    = 00010000
```

这表示“最右边的那个 0”的权值。

### 竖式感受 2：`x | (x - 1)` 和 `~x & (x + 1)`

先看 `x | (x - 1)`，取 `x = 10110000`：

```text
x         = 1 0 1 1 0 0 0 0
x - 1     = 1 0 1 0 1 1 1 1
------------------------
x | (x - 1) = 1 0 1 1 1 1 1 1
```

这说明右边连续的 0 被全部填成了 1。

再看 `~x & (x + 1)`，取 `x = 10101111`：

```text
x         = 1 0 1 0 1 1 1 1
~x        = 0 1 0 1 0 0 0 0
x + 1     = 1 0 1 1 0 0 0 0
------------------------
~x & (x + 1) = 0 0 0 1 0 0 0 0
```

可以看到，最后只留下了最右边那个 0 对应的位置。

### 这些式子有什么用？

- 做状态转移时修改最右边某一段位；
- 写一些构造题；
- 做二进制规律观察题；
- 快速处理“连续 1”或“连续 0”。

先别急着死背，建议自己随手写几个二进制例子验证一下，印象会更深。

---

## 九、异或的高阶用法

异或在基础运算里看起来只是“不同为 1，相同为 0”，但它在算法里特别有力量，因为它满足下面这些重要性质：

- `a ^ a = 0`
- `a ^ 0 = a`
- 满足交换律和结合律

这意味着：

> 相同的数异或两次会被“抵消掉”。

### 1. 找出只出现一次的数

如果一个数组里，除了一个数外，其余每个数都出现两次，那么把所有数异或起来，最后剩下的就是那个只出现一次的数。

例如：

```text
12 ^ 7 ^ 9 ^ 12 ^ 7 = 9
```

因为 `12 ^ 12 = 0`，`7 ^ 7 = 0`，只剩 `9`。

### 竖式感受：为什么异或能把成对元素消掉

还是看：

```text
12 ^ 7 ^ 9 ^ 12 ^ 7
```

利用交换律和结合律，我们可以先把相同的数挪到一起：

```text
12 ^ 7 ^ 9 ^ 12 ^ 7
= 12 ^ 12 ^ 7 ^ 7 ^ 9
=  0 ^  0 ^ 9
= 9
```

所以异或在“找只出现一次的数”这类题里特别好用，因为成对元素会自动抵消。

代码：

```cpp
int singleNumber(const vector<int>& a) {
    int ans = 0;
    for (int x : a) ans ^= x;  // 成对元素会两两抵消
    return ans;  // 最后剩下的就是只出现一次的数
}
```

### 2. 找出两个只出现一次的数

如果数组里恰好有两个数只出现一次，其他数都出现两次，那么：

1. 先异或全部元素，得到 `xor_all = p ^ q`；
2. `p` 和 `q` 至少有一位不同，所以 `xor_all` 至少有一位是 1；
3. 取出这最低位的 1：`low = xor_all & -xor_all`；
4. 用这 1 位把所有数分成两组；
5. 两组内分别异或，就能分别得到 `p` 和 `q`。

代码：

```cpp
pair<int, int> twoSingles(const vector<int>& a) {
    int xor_all = 0;
    for (int x : a) xor_all ^= x;  // 得到两个目标数的异或值

    int low = xor_all & -xor_all;  // 取出它们最低位上不同的那一位
    int p = 0, q = 0;
    for (int x : a) {
        if (x & low) p ^= x;  // 这一组中成对元素抵消后，剩下其中一个目标数
        else q ^= x;  // 另一组同理
    }
    if (p > q) swap(p, q);  // 输出时按从小到大排列
    return {p, q};
}
```

### 3. 不用 `+` 求两数之和

这也是一道经典题。

思路：

- `a ^ b` 相当于“不进位加法”；
- `(a & b) << 1` 就是所有进位；
- 不断把“当前和”和“进位”重新相加，直到没有进位。

代码：

```cpp
int addWithoutPlus(int a, int b) {
    while (b != 0) {
        unsigned int carry = (static_cast<unsigned int>(a & b) << 1);  // 先算出进位
        a = a ^ b;  // 再算不带进位的和
        b = static_cast<int>(carry);  // 下一轮继续把进位加进去
    }
    return a;
}
```

### 对应程序 4：异或工具箱

下面程序演示三个常见功能：单异常数、双异常数、无加号求和。

```cpp
#include <bits/stdc++.h>
using namespace std;

int singleNumber(const vector<int>& a) {
    int ans = 0;
    for (int x : a) ans ^= x;  // 成对出现的数会两两抵消
    return ans;  // 最后剩下的就是只出现一次的数
}

pair<int, int> twoSingles(const vector<int>& a) {
    int xor_all = 0;
    for (int x : a) xor_all ^= x;  // 得到两个目标数的异或值

    int low = xor_all & -xor_all;  // 取出二者最低位上不同的那一位
    int p = 0, q = 0;
    for (int x : a) {
        if (x & low) p ^= x;  // 这一组里成对元素抵消，剩下其中一个目标数
        else q ^= x;  // 另一组同理
    }
    if (p > q) swap(p, q);  // 方便输出时从小到大
    return {p, q};
}

int addWithoutPlus(int a, int b) {
    while (b != 0) {
        unsigned int carry = (static_cast<unsigned int>(a & b) << 1);  // 这一轮产生的进位
        a = a ^ b;  // 不进位加法
        b = static_cast<int>(carry);  // 下一轮继续把进位加进去
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;  // 读入数组长度
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];  // 读入数组元素

    cout << singleNumber(a) << '\n';  // 输出“只出现一次”的单个数

    pair<int, int> ans = twoSingles(a);
    cout << ans.first << ' ' << ans.second << '\n';  // 输出两个只出现一次的数

    int x, y;
    cin >> x >> y;  // 再读入两个整数，演示无加号求和
    cout << addWithoutPlus(x, y) << '\n';
    return 0;
}
```

---

## 十、状态压缩：把“选或不选”压成一个整数

这已经是竞赛和算法里非常重要的一类位运算应用了。

### 1. 什么叫状态压缩？

如果有 $n$ 个对象，每个对象只有两种状态：

- 选 / 不选
- 在 / 不在
- 开 / 关

那么就可以用一个整数的二进制位来表示整个状态。

例如有 4 个学生，编号为 0、1、2、3：

```text
mask = 0101
```

表示：

- 第 0 位是 1，选了 0 号；
- 第 1 位是 0，没选 1 号；
- 第 2 位是 1，选了 2 号；
- 第 3 位是 0，没选 3 号。

### 2. 集合运算和位运算的对应关系

设 `A`、`B` 都是状态压缩后的整数，则：

- 并集：`A | B`
- 交集：`A & B`
- 对称差：`A ^ B`
- 差集（A 去掉 B）：`A & ~B`

### 3. 枚举所有子集

如果一共有 $n$ 个元素，那么所有子集一共有 $2^n$ 个，对应的状态正好就是：

```cpp
for (int mask = 0; mask < (1 << n); ++mask) {
    // mask 表示一种选法
}
```

每个 `mask` 都代表一种方案。

### 4. 枚举某个集合 S 的所有子集

这是更高阶、也更常考的一种写法：

```cpp
for (int sub = S; ; sub = (sub - 1) & S) {
    // sub 是 S 的一个子集
    if (sub == 0) break;
}
```

它的作用是：

> 按从大到小的顺序，把 `S` 的所有子集恰好枚举一遍。

### 演示

设：

```text
S = 1101
```

那么它的子集会依次枚举出：

```text
1101
1100
1001
1000
0101
0100
0001
0000
```

这些数正好都是 `1101` 的子集状态。

### 竖式感受：为什么 `(sub - 1) & S` 能继续跳到下一个子集

还是取 `S = 1101`，看前两步：

```text
sub           = 1 1 0 1
sub - 1       = 1 1 0 0
(sub - 1) & S = 1 1 0 0
```

继续下一步：

```text
sub           = 1 1 0 0
sub - 1       = 1 0 1 1
(sub - 1) & S = 1 0 0 1
```

可以发现：

- `sub - 1` 会先把最低位的 1 消掉；
- 再和 `S` 按位与，就会把不属于 `S` 的那些位全部抹掉；
- 于是就自然跳到了下一个合法子集。

### 对应程序 5：用状态压缩枚举所有选法

下面是一个很典型的“子集枚举”程序。

题意模型：有 $n$ 个活动，每个活动有一个得分，最多能选若干个，要求总分不超过上限 `limit`，问最大总分是多少。

为了方便演示，下面先假设 `n <= 20`。

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, limit;
    cin >> n >> limit;  // 读入活动个数和分数上限
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];  // 读入每个活动的得分

    int best = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) {
                sum += a[i];  // 第 i 位是 1，说明第 i 个活动被选中
            }
        }
        if (sum <= limit) {
            best = max(best, sum);  // 在不超上限的前提下更新最优答案
        }
    }

    cout << best << '\n';  // 输出最大可行总分
    return 0;
}
```

这个程序就是“状态压缩 + 枚举所有子集”的最经典入门模型。

---

## 十一、位运算中的常见坑

高阶位运算很强，但也很容易出错。下面这些坑必须提前知道。

### 1. 混合运算时一定加括号

例如：

```cpp
a & b == 0
```

这不是你想的 `(a & b) == 0`，而是：

```cpp
a & (b == 0)
```

正确写法必须是：

```cpp
(a & b) == 0
```

### 2. 讨论纯位模式时，优先使用无符号数

```cpp
unsigned int x;
```

这样可以避开一部分负数右移、符号扩展之类的问题。

### 3. 写掩码时尽量写 `1u` 或 `1ull`

例如：

```cpp
1u << k
1ull << k
```

比 `1 << k` 更稳，因为 `1` 默认是 `int`，移位太高时可能出问题。

### 4. 不要拿 `pow(2, k)` 代替 `1 << k`

`pow` 是浮点运算，既慢又可能有精度问题。

如果你想得到 $2^k$，应直接写：

```cpp
1u << k
```

### 5. `k` 不能乱取

如果是 32 位整数，`k` 最好控制在 `0` 到 `30` 或 `31` 的合理范围内。超出位宽去移位，会产生未定义行为或不符合预期的结果。

### 6. 异或交换知道即可，不建议滥用

```cpp
a ^= b;
b ^= a;
a ^= b;
```

虽然能交换，但可读性差，还容易在 `a` 和 `b` 指向同一位置时出问题。正常写题，直接 `swap(a, b)` 更好。

### 7. `unsigned` 只适合讨论“非负数位模式”

如果题目本身涉及负数语义，比如有符号数大小比较、带符号右移效果，就不能简单地一股脑全换成 `unsigned`。

这一节之所以大量使用 `unsigned`，是因为重点在“观察位”“操作位”“利用二进制规律”。

### 8. `unsigned long long` 写移位更安全，但也不是无限大

```cpp
1ull << k
```

确实比 `1 << k` 安全得多，但它仍然只有 64 位。若 `k` 取得太离谱，依然会出问题。

### 9. `bitset` 适合辅助观察，但不适合硬套到所有题里

如果你只是想把一个数的二进制打印出来，`bitset` 很方便；但如果题目核心是 `lowbit`、清最低位的 1、连续 0/1 的构造，这些操作直接用整数写通常更短、更清楚。

课堂里最容易犯的错，就是为了“看起来高级”而硬把整数题改写成 `bitset` 题，结果把本来简单的规律绕复杂了。

---

## 十二、课堂速查表

下面把这一节最常用的表达式放在一起，方便查阅。

| 表达式 | 含义 |
|:--|:--|
| `unsigned int x;` | 适合 32 位无符号位运算 |
| `unsigned long long x;` | 适合 64 位无符号位运算 |
| `x | (1u << k)` | 把第 k 位设为 1 |
| `x & ~(1u << k)` | 把第 k 位设为 0 |
| `x ^ (1u << k)` | 把第 k 位翻转 |
| `(x >> k) & 1u` | 读取第 k 位 |
| `x & ((1u << k) - 1)` | 保留末 k 位 |
| `x & ~((1u << k) - 1)` | 清空末 k 位 |
| `(x >> l) & ((1u << (r - l + 1)) - 1)` | 取出第 l 到第 r 位 |
| `x & (-x)` | 只保留最低位的 1 |
| `x & (x - 1)` | 清掉最低位的 1 |
| `x > 0 && (x & (x - 1)) == 0` | 判断是否为 2 的幂 |
| `x & (x + 1)` | 把右边连续的 1 清零 |
| `x | (x + 1)` | 把右起第一个 0 变成 1 |
| `x | (x - 1)` | 把右边连续的 0 变成 1 |
| `~x & (x + 1)` | 取出最低位的 0 |
| `a ^ a = 0` | 相同的数异或会抵消 |
| `1u << k` | 构造 32 位掩码中的单个 1 |
| `1ull << k` | 构造 64 位掩码中的单个 1 |

---

## 十三、这一节学完后，应该会什么？

如果你已经能独立完成下面这些事，就说明这节真正学会了：

- 能说清 `unsigned int` 和 `unsigned long long` 的区别与用法；
- 能写出“设置某一位、清空某一位、翻转某一位、读取某一位”的代码；
- 能用掩码提取某一段二进制位；
- 能解释 `x & (-x)` 和 `x & (x - 1)` 的含义；
- 能写出判断 2 的幂、统计 1 的个数的程序；
- 能用异或解决“只出现一次”的题；
- 能把“选或不选”的问题写成状态压缩。

到这里，位运算就不再只是“会算”，而是真正进入“会用”的阶段了。