位运算题单
题单介绍
# $\text{Part 0. 前言}$
位运算是在二进制中进行的运算操作，包括按位与、按位或、按位异或、按位非、左移、右移等，能够快速解决一些运算，如 $2$ 的次幂，判断奇偶性等。
如果有好题或错误欢迎私聊。
# $\text{Part 1. And(\&) 运算}$
定义：$x\ \&\ y$（$x,y\in\{0,1\}$），当且仅当 $x=y=1$ 时值为 $1$，否则为 $0$。
- `x & 1`：
用处：求 $x$ 的奇偶性，$1$ 为奇，$0$ 为偶。
- `x & (1 << k)`：
用处：表示 $x$ 转换为二进制后，从后往前数第 $k+1$ 位。
- `x & ((1 << k) - 1)`：
用处：表示 $x$ 转换为二进制后，后 $k$ 位。
- `x &= (x - 1)`：
用处：消去 $x$ 最末尾的 $1$。
- `x & -x`（$\operatorname{lowbit}$ 运算）：
用处：$x$ 的二进制中最后一位 $1$ 以及后面的所有 $0$，常用于树状数组。
例题：
- [P7970 [KSN2021] Binary Sea](https://www.luogu.com.cn/problem/P7970)
- [P4310 绝世好题](https://www.luogu.com.cn/problem/P4310)
- [P10118 『STA - R4』And](https://www.luogu.com.cn/problem/P10118)
# $\text{Part 2. Or(|) 运算}$
定义：$x\ |\ y$（$x,y\in\{0,1\}$），当且仅当 $x=y=0$ 时值为 $0$，否则为 $1$。
- `x |= 1`：
用处：将 $x$ 变为 $2\left\lceil\dfrac x2\right\rceil$。
- `x = (x | 1) - 1`：
用处：将 $x$ 变为 $2\left\lfloor\dfrac x2\right\rfloor$。
- `x |= (1 << k)`：
用处：把 $x$ 的二进制从后往前数第 $k+1$ 位变为 $1$。
- `x |= ((1 << k) - 1)`：
用处：把 $x$ 二进制的后 $k$ 位变为 $1$。
例题：
- [P8569 [JRKSJ R6] 第七学区](https://www.luogu.com.cn/problem/P8569)
- [P7384 「EZEC-6」分组](https://www.luogu.com.cn/problem/P7384)
# $\text{Part 3. Xor(\ \^{}\ ) 运算}$
定义：$x\ \text{\^{}} \ y$（$x,y\in\{0,1\}$），当且仅当 $x\neq y$ 时值为 $1$，否则为 $0$。
重要性质：
1. `x ^ x = 0`。
1. `x ^ 0 = x`。
在异或中，这两个性质（尤其是第一个）用处非常广，如区间异或值可用提前预处理前缀异或代替，树上路径异或可用提前预处理到根的异或和。
- `x ^= 1`：
用处：最后一位取反。
- `x ^= (1 << k)`：
用处：第 $k+1$ 位取反。
- `x ^= (1 << k) - 1`：
用处：后 $k$ 位取反。
例题：
- [P6225 [eJOI2019] 异或橙子](https://www.luogu.com.cn/problem/P6225)
- [CF276D Little Girl and Maximum XOR](https://www.luogu.com.cn/problem/CF276D)
- [P6623 [省选联考 2020 A 卷] 树](https://www.luogu.com.cn/problem/P6623)
- [P4060 [Code+#1] 可做题](https://www.luogu.com.cn/problem/P4060)
- [P2420 让我们异或吧](https://www.luogu.com.cn/problem/P2420)
- [P1469 找筷子](https://www.luogu.com.cn/problem/P1469)
- [P6599 「EZEC-2」异或](https://www.luogu.com.cn/problem/P6599)
- [P7717 「EZEC-10」序列](https://www.luogu.com.cn/problem/P7717)
# $\text{Part 4. 非 (\~ ) 运算}$
定义：$~x$ 表示 $x$ 在二进制下每一位取反。
- `~(x - 1)`：
用处：取 $x$ 的相反数。
# $\text{Part 5. 左移运算}$
定义：`x << k` 表示在 $x$ 二进制的后面加上 $k$ 个 $0$。
- `1 << k`：
用处：表示 $2^k$。
- `x << 1`：
用处：即 $2x$。
- `x << 1 | 1`：
用处：即 $2x+1$（常用于线段树）。
# $\text{Part 6. 右移运算}$
定义：`x >> k` 表示删除 $x$ 二进制后 $k$ 位。
- `x >> 1`：
用处：表示 $x$ 除以 $2$ 向下取整。
# $\text{Part 7. 部分函数}$
## $\operatorname{lowbit} 函数$
可以用 `x & -x` 来实现，主要在树状数组中起作用。
## $\operatorname{popcount} 函数$
$\operatorname{popcount}(x)$ 表示 $x$ 在二进制中 $1$ 的个数，c++ 中提供库函数 `__builtin_popcountll`。实现原理是 `x & (x - 1)` 不为 $0$ 就个数加 $1$，代码如下：
```cpp
inline int popcount(int x) {
int cnt = 0;
while(x) {
x &= (x - 1);
++cnt;
}
return cnt;
}
```
现在的月赛也是越来越喜欢出关于 $\operatorname{popcount}$ 函数的题了，比如：
- [P9451 [ZSHOI-R1] 新概念报数](https://www.luogu.com.cn/problem/P9451)
- [P10114 [LMXOI Round 1] Size](https://www.luogu.com.cn/problem/P10114)
- [P10118 『STA - R4』And](https://www.luogu.com.cn/problem/P10118)
## $\text{bitset}$
$\text{bitset}$ 是一个 STL 容器，相当于一个二进制的数组，并且可以直接用 $\texttt{01}$ 串赋值。
定义方式：`bitset<N> b;`。$N$ 为 $b$ 的长度。
$\text{bitset}$ 支持所有位运算。
### $\operatorname{count}$ 函数
`b.count()` 用于求出 $b$ 中 $1$ 的个数。
### $\operatorname{size}$ 函数
`b.size()` 用于返回 $b$ 的大小。
### $\operatorname{any}$ 函数
`b.any()` 用于返回 $b$ 中是否有 $1$。
### $\operatorname{none}$ 函数
`b.none()` 用于返回 $b$ 是否所有位是 $0$。
### $\operatorname{all}$ 函数
`b.all()` 用于返回 $b$ 是否所有位是 $1$。
### $\operatorname{test}$ 函数
`b.test(p)` 用于返回 $b$ 的第 $p$ 位。
### $\operatorname{set}$ 函数
`b.set(p)` 可以将 $b$ 的第 $p$ 位设为 $1$。
### $\operatorname{reset}$ 函数
`b.reset(p)` 可以将 $b$ 的第 $p$ 位设为 $0$。
### $\operatorname{flip}$ 函数
`b.flip(p)` 可以将 $b$ 的第 $p$ 位取反。
### $\operatorname{to\_ulong}$ 函数
`b.to_ulong()` 可以将 $b$ 转换为无符号整数。
### $\operatorname{to\_string}$ 函数
`b.to_string()` 可以将 $b$ 转换为字符串。
例题：
- [B3695 集合运算 3](https://www.luogu.com.cn/problem/B3695)