\(\text{bit}\) 是度量信息的基本单位，只有 \(0\) 与 \(1\) 两种状态。计算机的一切运算无不归结于一个个 \(\text{bit}\) 的运算。熟练掌握并使用位运算，可以帮助我们理解程序运行的表现，提高算法效率，降低编程复杂度。
定义：对于二进制表示下的每一位，有
| \(\&\) | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
理解：每一位，若两者都为 \(1\)，答案为 \(1\)，否则为 \(0\)。
区分：逻辑与 \(\&\&\)。
定义：对于二进制表示下的每一位，有
| \(\mid\) | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
理解：每一位，若两者都为 \(0\)，答案为 \(0\)，否则为 \(1\)。
区分：逻辑或 || 。
(\(\large \texttt{C++}\) 中写作 ^ )
定义：对于二进制表示下的每一位，有
| \(\oplus\) | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
理解：每一位，若两者不同 \(1\)，答案为 \(1\)，否则为 \(0\)。
理解 \(\text{ex}\)：二进制下的不进位加法。这种思想有时会作为一种 \(\text{trick}\) 出现在题目中。
定义：在二进制下直接将该数按位取反。
公式：\(\sim S = -1-S\)，亦及 \(\left\vert (\sim S) - (-S)\right\vert =1\)。
区分：与 \(-S\) 区分。 \(-S\) 指的是将该数的每一位取反。
使用：for (int i = n; i >= 0; --i) 可简写成 for (int i = n; ~i; --i)。
定义：在二进制下把数字同时向左移动，低位以 \(0\) 填充，高位越界舍弃。
公式：\(1 \ll n = 2^n, n\ll1=2n\)。
定义：在二进制补码下把数字同时向右移动，高位以符号位填充，低位越界舍弃。
公式：\(n \gg 1 = \lfloor \dfrac{n}{2.0}\rfloor\)。
区分：第一，\(\large\texttt{C++}\) 中的 / 运算符是向 \(0\) 取整，在涉及负数域的二分时会失误；第二，算术右移与逻辑右移有细微差别，一般的编译器都是算术右移，无特殊说明我们也使用算术右移。
定义：高位以 \(0\) 填充，其他与算术右移无区别。
给定 \(1 \leq a, b, p \leq 10^9\)，请求出 \(a ^ b \bmod p\)。
考虑暴力求解：累乘 \(a\)。
时间复杂度 \(\text{O}(b)\)，无法接受。
我们将 \(b\) 拆解为 \(2 ^ {k_1}+2^{k_2}+2^{k_3}+\dots+2^{k_m}\)。
我们只需要让 \(i\) 从 \(0 \sim \log_2b\) 循环，若 \(b\) 的当前位为 \(1\)，则 \(ans \leftarrow ans+a^{2^{i}} \bmod p\)。
我们考虑在 \(i\) 循环的同时也将 \(a\) 更新：\(a \leftarrow a \times a \bmod p\)，这样便可以实时回答 \(a^{2^i}\)。
时间复杂度 \(\text{O}(\log_2 b)\)，可以 \(\large \texttt{AC}\)。
我们设计子问题 \(f(x) = a^x \bmod p\)，
则容易得到递归的公式：
\(x \mid 2\)：\(f(x) = f(x / 2) \times f(x / 2) \bmod p\)
\(x \nmid 2\)：\(f(x) = f(x \gg 1) \times f(x \gg 1) \times a \bmod p\)
递归的初始条件：\(f(0) = 1\)
这样，我们也可以 \(\text{O}(\log_2b)\) 求出答案。
平时尽量使用迭代的方法，这样常数小；
注意数据范围，常取模。
int Power(int a, int b, int p) {
int res = 1 % p;
for (; b; b >>= 1) {
if (b & 1) {
res = 1ll * res * a % p;
}
a = 1ll * a * a % p;
}
return res;
}
我们考虑维护快速幂的数据类型需要有什么运算律：
综上，我们有如下几种可维护的快速幂：
还有很多运算满足，此处不再赘述。
我们修改限制条件为 \(a, b \leq 10^{18}\)，是否有正确的算法计算 \(a ^ b \bmod p\) 的精确值？
在不使用高精度或 python，Ruby 等支持高精的语言情况下，答案是否定的。
但是，我们可以解决 \(a\times b \bmod p\) 这个问题。
我们使用快速幂维护加法，答案即为 \(a \times b \bmod p\)，时间复杂度 \(\text{O}(\log_2 \min(a, b))\)。
我们考虑使用 long double 存储 \(c = a \times b / p\)，long long 存储 \(C = \lfloor c\rfloor\) 和 \(ans = a \times b - C \times p\)。
正确性：我们只关心 \(c\) 的高若干位，故用 long double 舍弃低位，\(a \times b\) 与 \(C \times p\) 的差一定在 \(0 \sim p - 1\) 之间，所以我们只关心它们分别的低若干为，使用 long long 舍弃高位。
二进制状态压缩，是指将一个 vector<bool> 保存为 int 来减少时间复杂度，空间复杂度的方法。
| 操作 | 运算 |
|---|---|
| 取出 \(n\) 的第 \(k\) 位 | \((n\gg k)\&1\) |
| 取出 \(n\) 的后 \(k\) 位 | \(n\&((1\ll k)-1)\) |
| \(n\) 的第 \(k\) 位取反 | \(n \oplus\!\!= (1\ll k)\) |
| \(n\) 的第 \(k\) 位赋值 \(1\) | \(n \mid=(1 \ll k)\) |
| \(n\) 的第 \(k\) 位赋值 \(0\) | \(n \ \&\!\!= (\sim(1<<k))\) |
（补充：v.size() 较大时，可以使用 \(\large \texttt{STL}\) 内置的 \(\text{bitset}\)。）
我们将通过一道例题来说明它的重要性。
定义 \(\text{Hamilton}\) 路径为不重不漏经过点 \(0 \sim n - 1\) 恰好各一次的路径。
给定 \(n (1\leq n\leq 20)\) 的带权无向图，请求出从 \(0\) 到 \(n - 1\) 的最短 \(\text{Hamilton}\) 路径。
这道题应该是状压 \(\text{DP}\) 的模板题。
设计状态 \(f_{i, j}\)：经过的点的状态为 \(i\) （经过点 \(x\) 则 \(i\) 的第 \(x\) 位为 \(1\)），当前在点 \(j\)。
易得状态转移方程：
注意条件：\((i \gg j) \& 1\) 且 \(((i \oplus (i \ll j)) \gg k) \& 1\)。
const int kMaxN = 20;
int n, a[kMaxN][kMaxN];
int f[1 << kMaxN][kMaxN];
int Solve() {
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for (int i = 1; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
if ((i >> j) & 1) {
for (int k = 0; k < n; ++k) {
if (((i ^ (1 << j)) >> k) & 1) {
f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + a[k][j]);
}
}
}
}
}
return f[(1 << n) - 1][n - 1];
}
二进制表示下位运算不进位。
例题：起床困难综合症
选择 \(\left[0, m\right]\) 中的一个整数 \(x_0\)，使得其经过给定的 \(n\) 次位运算，结果 \(x\) 最大。
由于位运算不进位，我们将 \(30\) 位拆开考虑。
由高到低考虑，对于每一位，\(\text{O}(n)\) 算出其取 \(0, 1\) 后最终对应位置上的值。若能使得最后此位为 \(1\) 且 \(x_0 \leq m\)，就选；否则不选。
const int kMaxN = 1e5 + 5;
int n, m;
pair<string, int> opt[kMaxN];
bool calc(int x, bool st) {
for (int i = 1; i <= n; ++i) {
int tmp = (opt[i].second >> x) & 1;
if (opt[i].first == "AND") {
st &= tmp;
}
else if (opt[i].first == "OR") {
st |= tmp;
}
else {
st ^= tmp;
}
}
return st;
}
int Solve() {
int ans = 0, val = 0;
for (int i = 29; ~i; --i) {
bool tmp0 = calc(i, 0), tmp1 = calc(i, 1);
if (tmp1 > tmp0 && ans + (1 << i) <= m) {
ans += (1 << i), val += (1 << i);
}
else {
val += (tmp0 << i);
}
}
return val;
}
\(\bold\oplus\)成对变换。
即 \((0, 1), (2, 3), \dots\)，只要是 \((2k, 2k+1)\)，都满足一个数 \(\oplus 1\) 得到另一个数。
这一性质常用于图论中链式前向星反向边存储。
我们发现可以 \(\text{O}(1)\) 计算出 lowbit(x) 的值，其中 lowbit(x) 指的是 \(x\) 二进制表示下最低位 \(1\) 的位权。
有公式 \(\text{lowbit}(x) = x \& -x\)，证明略。
lowbit 配合 Hash 可以找出一个整数二进制下所有的 \(1\)，时间复杂度与 \(1\) 的数量同级。
此外，lowbit 还是树状数组中一个重要的运算。
原文：https://www.cnblogs.com/reliauk/p/0x01.html