重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
位运算
习题AcWing216，P2114，例题P4310，K2192(最大and值)，P8019
0x01 位运算
位运算和按位贪心是常用的计算和优化手段。其中，按位枚举可以将线性级别的枚举优化至 \(\log\) 级别；由于二进制的独特性质 \(2^0+2^1+\cdots+2^{k-1}<2^k\)，也让从高位到低位的按位贪心成为了可能。本文接下来将介绍一系列的位运算基本技巧，并结合例题分析位运算优化的运用。
创新互联服务项目包括宝山网站建设、宝山网站制作、宝山网页制作以及宝山网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，宝山网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到宝山省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
位运算技巧
位运算的基本运算符为：&, |, ^, <<, >>, ~，分别表示按位与、或、异或、左移，右移，取反。需要注意的是，由于位运算的优先级较低，运算时最好加上括号。
假设二进制位的最低位为第 \(0\) 位，当前的数为 \(x\)，则
- 将 \(x\) 左移，右移一位：
x << 1，x >> 1; - 将 \(x\) 最后一位变为 \(1,0\)：
x | 1，(x|1) - 1; - 将 \(x\) 二进制第 \(k\) 位变为 \(1,0\)：
x | (1 << k)，x (& ~(1 << k)); - 将 \(x\) 二进制后 \(k\) 位变为 \(1,0\)：
x | ((1< - 取 \(x\) 的第 \(k\) 位：
(x >> k) & 1 - \(\operatorname{lowbit}(x)=x \text & (-x)\)
例题
P4310 绝世好题: 给定一个长度为 \(n\) 的数列 \(a_i\)，求 \(a_i\) 的子序列 \(b_i\) 的最长长度 \(k\)，满足 \(b_i \& b_{i-1} \ne 0\)，其中 \(2\leq i\leq k\)，& 表示位运算取与。
这道题明显是一个有关序列分割的动态规划题目。设 \(f_i\) 表示前 \(i\) 项的最大长度且 \(i\) 必选，那么 \(f_i=\max_{j
利用位运算，我们可以不要枚举上一个位置 \(j\)，而是枚举二进制下哪一位与 \(a_i\) 取与后为 \(1\)。
具体地，我们设 \(g[i,p]\) 表示前 \(i\) 项最终第 \(p\) 位为 \(1\) 的最大长度。则，我们可以枚举所有 \(a_i\) 的二进制为 \(1\) 的位置，即 \(f_i=\max\{g[i-1,p]\ |\ a_i\text{的第p位为1}\}\)。然后，对于 \(g[i,p]\)，若 \(a_i\) 的第 \(p\) 位为 \(0\)，那么 \(g[i,p]\leftarrow g[i-1,p]\)，否则 \(g[i,p]\leftarrow \max(g[i-1,p],f_i)\)。
容易发现，\(g_i\) 数组的取值仅与 \(g_{i-1}\) 有关，因此可以通过滚动数组的方式优化空间。总的时间复杂度为 \(O(n\log \omega)\)，空间复杂度为 \(O(n+\log \omega)\)，其中 \(\omega\) 表示值域。
P4310 代码
int n, a, f, g[2][31];
/*
f[i] 表示以 i 结尾的最长子序列长度
g[i, p]表示前 i项第p位为1的最大长度
f[i] = max{g[i-1, p] | a[i]第p位为1} + 1
g[i, p] =
max(g[i-1, p], f[i]), a[i]第p位为1
g[i-1, p], a[i]->p = 0
优化：g[i, p]第一维滚动
*/
int main () {
int ans = 0;
read(n);
rep(i, 1, n) {
read(a);
f = 1;
rep(p, 0, 30)
if((a >> p) & 1)
f = max(f, g[(i - 1) & 1][p] + 1);
rep(p, 0, 30)
if((a >> p) & 1)
g[i & 1][p] = max(g[(i - 1) & 1][p], f);
else g[i & 1][p] = g[(i - 1) & 1][p];
ans = max(ans, f);
}
writeln(ans);
return 0;
}
按位取与: 给定一个长度为 \(n\) 的序列 \(a_i\)，请你求出 \(\max\{a_i\&a_j\}\)，其中 \(1\le i
本题暴力的复杂度为 \(O(n^2)\)，显然无法通过。此时，我们需要利用按位贪心的思想。按位贪心是指从高位到低位遍历，优先使得高位为 \(1\)，只有高位无法为 \(1\) 时才使这一位为 \(0\)，并继续按此法则考虑下一位。其正确性证明如下：
假设目前考虑最高位为第 \(k\) 位，当第 \(k\) 位为 \(1\) 而后 \(k-1\) 位均为 \(0\) 时，收益为 \(2^k\)；当第 \(k\) 位为 \(0\) 而后 \(k-1\) 位均为 \(1\) 时，收益为 \(2^{k-1}+2^{k-2}+\cdots+2^0\)。利用等比数列求和公式可得，后者等于 \(2^k-1<2^k\)，因此高位为 \(1\) 更优。
对于本题，由于每一位之间的计算互相独立，可以从高到低按位贪心。假设目前访问到第 \(p\) 位，如果第 \(p\) 位为 \(1\) 的数的个数 \(\ge 2\)，那么最终答案里该位为 \(1\)。此时，所有第 \(p\) 位为 \(0\) 的数都不再参与后续的计算。因此，我们可以用两个动态数组 vector 存储当前轮合法的数和下一轮合法的数，并用滚动数组的方式传递；若数组大小 \(\ge 2\) 则将 \(ans\) 的第 \(p\) 位置为 \(1\)（ans |= (1ll<
这样，时间复杂度为 \(O(n\log \omega)\)，空间复杂度为 \(O(n)\)。需要注意的是，由于值域达到 long long 的范围，而 c++ 中整数默认的类型为 int，左移操作时需要使用 1ll 而非 1，这也是我在 CSP2020 时曾经犯下的错误。
部分代码
ll n, a[maxn], ans, now;
vector id[2];
int main () {
read(n);
rep(i, 1, n) read(a[i]), id[0].push_back(i);
Rep(p, 30, 0) {
ll nxt = (now ^ 1);
id[nxt].clear();
for(unsigned int i = 0; i < id[now].size(); i++) {
int u = id[now][i];
if((1ll << p) & a[u])
id[nxt].push_back(u);
}
if(id[nxt].size() < 2) continue;
ans |= (1ll << p);
now = nxt;
}
writeln(ans);
return 0;
}
当然，你也可以对本题所求的内容进行拓展，比如求两两 \(\text{and, or, xor}\) 的最大值，并提交到 there。事实上，异或的最大值本质上也是按位贪心，辅以 \(01Trie\)；位或的最大值则需要数位 DP。
分享题目：位运算
本文URL：http://cqcxhl.cn/article/dsoihso.html