位运算

习题AcWing216,P2114,例题P4310,K2192(最大and值),P8019

0x01 位运算

位运算和按位贪心是常用的计算和优化手段。其中,按位枚举可以将线性级别的枚举优化至 \(\log\) 级别;由于二进制的独特性质 \(2^0+2^1+\cdots+2^{k-1}<2^k\),也让从高位到低位的按位贪心成为了可能。本文接下来将介绍一系列的位运算基本技巧,并结合例题分析位运算优化的运用。

创新互联服务项目包括宝山网站建设、宝山网站制作、宝山网页制作以及宝山网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,宝山网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到宝山省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!

位运算技巧

位运算的基本运算符为:&, |, ^, <<, >>, ~,分别表示按位与、或、异或、左移,右移,取反。需要注意的是,由于位运算的优先级较低,运算时最好加上括号。

假设二进制位的最低位为第 \(0\) 位,当前的数为 \(x\),则

  • \(x\) 左移,右移一位:x << 1x >> 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。这样朴素的动态规划转移的时间复杂度是 \(O(n^2)\),无法通过全部的测试点。

利用位运算,我们可以不要枚举上一个位置 \(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\(a_i\le 10^{18}\)

本题暴力的复杂度为 \(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。


当前名称:位运算
文章起源:http://pwwzsj.com/article/dsoihso.html