1223 lines
28 KiB
Markdown
1223 lines
28 KiB
Markdown
# 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 的个数的程序；
|
||
- 能用异或解决“只出现一次”的题；
|
||
- 能把“选或不选”的问题写成状态压缩。
|
||
|
||
到这里，位运算就不再只是“会算”，而是真正进入“会用”的阶段了。
|