屑曾的ACM笔记（1）-位运算、线性基

一、位运算公式及证明1.公式概览功能公式加法aba⊕b2×(ab)减法a−ba⊕b−2×(∼ab)判断异号(a⊕b)0交换两数a ^ b; b ^ a; a ^ b;求绝对值mask x 31; return (x ^ mask) - mask;判断2的幂n 0 (n (n-1)) 0清除最低位1n (n-1)提取最低位1n (-n)2.公式详细证明i. 加法公式aba⊕b2×(ab)证明二进制加法中每一位的计算分为两步本位和不进位等于两个比特的异或结果 ai​⊕bi​。进位只有当两个比特都是1时才产生进位即 ai​bi​并且这个进位要加到高一位上相当于左移一位即乘以2。将所有位求和ab∑(ai​⊕bi​)⋅2i∑(ai​bi​)⋅2i1(a⊕b)2×(ab)举例a5(101),b3(011)a⊕b1106ab001162×18与 538 一致。ii. 减法公式a−ba⊕b−2×(∼ab)证明减法中的借位发生在 ai​0,bi​1 的位上即 ∼ai​bi​。借位会向高位传播相当于从高位减去 2i1。因此a−b(a⊕b)−2×(∼ab)举例a5(101),b3(011)a⊕b1106∼a010∼ab01026−2×22与 5−32 一致。iii. 判断异号(a⊕b)0证明整数的最高位符号位为1表示负数。a⊕b 的最高位为1当且仅当 a 和 b 的最高位不同一个0一个1。最高位不同意味着一个非负含0一个负数即异号。因此 (a⊕b)0 等价于 a 与 b 异号。注意0被视为非负0⊕负数 结果为负数符合“异号”定义。iv. 交换两数不用临时变量a ^ b; // a x ^ y b ^ a; // b (x ^ y) ^ y x a ^ b; // a (x ^ y) ^ x y证明设初始 ax,by。第一步ax⊕y第二步ba⊕y(x⊕y)⊕yx⊕(y⊕y)x⊕0x第三步aa⊕b(x⊕y)⊕xy⊕(x⊕x)y⊕0y最终 ay,bx。依赖性质异或满足交换律、结合律且 x⊕x0x⊕0x。v. 求绝对值mask x 31; return (x ^ mask) - mask;证明若 x≥0mask 0(x ^ 0) - 0 x正确。若 x0mask -1全1x ^ (-1) \sim x按位取反再减去 (−1) 即加1得到 ∼x1。这正是负数的补码绝对值取反加一。因此结果总是 ∣x∣。vi. 判断2的幂n 0 (n (n-1)) 0证明2的幂的二进制形如100...0只有一个1。n−1 会将这个1变成0后面所有0变成1例如1000 → 0111。两者按位与1000 0111 0000。反之若 n 不是2的幂则至少有两位为1那么 n(n−1) 至少保留一个1结果不为0。加上 n0 排除0的情况0不是2的幂且 0(−1)0 会误判。vii. 清除最低位1n (n-1)证明设 n 的最低位的1在第 k 位从0开始即 n 的二进制为...100...0k个0。则 n−1 为...011...1k个1。按位与后第 k 位100更高位不变更低位的0与1得0。因此结果比 n 少了那个最低位的1其余位不变。举例n12(1100)n−111(1011)1100101110008。viii. 提取最低位1lowbitn (-n)证明在补码中−n∼n1。设 n 的最低位的1在第 k 位即 n…100…0。则 ∼n…011…1加1得 …100…0第 k 位恢复为1更低全0。第 k 位n 为1−n 也为1进位到达该位。第 k 位以上n 与 −n 相反因取反。第 k 位以下n 为0−n 也为0。因此 n(−n) 只在第 k 位得1其余位均为0。举例n12(1100)−12 的补码8位为11110100但低4位为01001100010001004。3.基础概念详解i. 什么是补码计算机用固定位数存储整数为了表示负数引入了补码系统。正数原码即其二进制表示最高位为0。负数其绝对值的补数即 2n−∣负数∣n为位数。简便计算取反加一。例如求 −5 的8位补码5的二进制00000101取反11111010加111111011← 这就是 −5。关键性质最高位是符号位0表示非负1表示负数。所有负数的最高位都是1。全1的二进制如11111111代表 −1因为 1(−1)0而00000001 11111111 1 00000000溢出后为0。ii. 算术右移为什么能把符号位移到数字位右移操作有两种逻辑右移左边补0。算术右移左边补符号位最高位的值目的是保持负数右移后仍为负数。对于32位整数x 31若 x≥0最高位为0算术右移31次后所有位都变成0结果为0。若 x0最高位为1算术右移31次后所有位都变成1结果为 −1全1。所以x 31就像“符号检测器”正数得0负数得-1。iii. 为什么算术右移不等价于除以2算术右移一位等价于向下取整的除法向负无穷方向而C语言的整数除法/是向零取整。正数时两者一致。负数时例如 −5算术右移得 −3向下取整而 −5/2 得 −2向零取整。因此用位运算实现向零取整的除以2需额外处理int trunc_div2(int x) { return (x 1) ((x 31) 1); // 负数时加1修正 }其中(x 31) 1在负数时为1正数时为0。iv. 什么是掩码掩码Mask是一个二进制数用于提取或修改特定位。例如0x80000000最高位为1其余0可提取符号位。而x 31得到的0或-1也是一种掩码0 保持原数不变。-1全1可与原数异或实现取反再减-1实现加1从而完成绝对值操作。二、线性基详解线性基是线性代数中的一个核心概念指向量空间中一组线性无关的向量且能张成整个子空间。在算法竞赛与数据处理中异或线性基XOR basis是最常见的应用——它将每个整数视为 F2​ 上的二进制向量通过维护一组基来高效解决最大异或和、第 k 小异或值、判断某个数能否被表示等问题。下面分别介绍两种构造方式普通消元贪心插入​ 与高斯消元行阶梯形并给出 C 代码演示。1.普通消元构造贪心插入原理从高位向低位维护一组基basis[i]表示最高位为第i位的基向量。每次插入一个新数x从高到低遍历每一位如 63 → 0。若x的第i位为 1如果basis[i]不存在则将x存入basis[i]结束插入。否则令x ^ basis[i]继续向下消去。最终x要么成为新的基要么变为 0表示能被已有基表示。这种构造保证了基向量最高位互不相同且每个基向量的最高位只出现在自己身上。特点时间复杂度 O(nlogM)其中 M 为值域。适合动态插入、查询最大异或和、判断存在性。得到的基不一定是行最简形但足够用于常见操作。C 代码普通消元#include bits/stdc.h using namespace std; using ll long long; const int MAXB 60; // 假设数值范围 ≤ 2^60 struct LinearBasis { ll basis[MAXB 1]; // basis[i] 存储最高位为 i 的基 LinearBasis() { memset(basis, 0, sizeof(basis)); } // 插入一个数 void insert(ll x) { for (int i MAXB; i 0; --i) { if (!(x i 1)) continue; if (!basis[i]) { basis[i] x; return; } x ^ basis[i]; } // 若 x 变成 0说明已被表示不做任何事 } // 查询最大异或和 ll queryMax() { ll res 0; for (int i MAXB; i 0; --i) if ((res ^ basis[i]) res) res ^ basis[i]; return res; } // 判断 x 是否能被表示 bool contain(ll x) { for (int i MAXB; i 0; --i) if (x i 1) { if (!basis[i]) return false; x ^ basis[i]; } return true; } }; // 使用示例 int main() { vectorll nums {5, 7, 10, 13}; LinearBasis lb; for (ll v : nums) lb.insert(v); cout 最大异或和: lb.queryMax() endl; // 输出 15 (1111) cout 6 是否可表示? lb.contain(6) endl; // 1 (true) return 0; }2.高斯消元构造行阶梯形原理将所有的数作为行向量组成一个 n×m 的矩阵m 为位数然后执行高斯消元化为行最简阶梯形RREF。具体步骤对每一列从高位到低位寻找主元。若找到非零行交换到当前行并用它消去下方所有行的该位。最后所有非零行就是一组线性基且它们是两两正交最高位唯一的简化形式。相比普通消元高斯消元会重新排列基的顺序并将每个基向量除了最高位外其他位也尽量消干净得到更规整的基例如用于求第 k 小异或值时更方便。特点时间复杂度 O(n⋅m)m 为位数常数。适用于离线处理一次性给出所有数。结果可用于求第 k 小异或值、线性空间的维数等。C 代码高斯消元构造#include bits/stdc.h using namespace std; using ll long long; const int MAXB 60; struct GaussBasis { vectorll basis; // 存储行最简形基向量 // 对所有数执行高斯消元 void build(const vectorll nums) { vectorll mat nums; // 拷贝一份 int row 0; for (int col MAXB; col 0; --col) { // 寻找当前列的主元 int sel -1; for (int i row; i (int)mat.size(); i) { if (mat[i] col 1) { sel i; break; } } if (sel -1) continue; swap(mat[row], mat[sel]); // 换到当前行 // 用主元消去下方所有行的该位 for (int i row 1; i (int)mat.size(); i) { if (mat[i] col 1) mat[i] ^ mat[row]; } // 可选消去上方行的该位得到 RREF for (int i 0; i row; i) { if (mat[i] col 1) mat[i] ^ mat[row]; } row; } // 取出所有非零行作为基 basis.clear(); for (int i 0; i row; i) if (mat[i] ! 0) basis.push_back(mat[i]); // 此时 basis 已经按最高位降序排列且每个基的最高位唯一 } // 查询最大异或和直接异或所有基即可 ll queryMax() { ll res 0; for (ll v : basis) res ^ v; return res; } // 查询第 k 小异或值需要进一步处理此处略 }; // 使用示例 int main() { vectorll nums {5, 7, 10, 13}; GaussBasis gb; gb.build(nums); cout 基向量个数: gb.basis.size() endl; // 2 cout 最大异或和: gb.queryMax() endl; // 15 for (ll v : gb.basis) { cout bitset4(v) ; // 1011 (11), 0100 (4) } cout endl; return 0; }3.两种构造方式的对比特性普通消元贪心插入高斯消元行阶梯形适用场景动态插入、在线查询离线构建、需要规整基时间复杂度O(nlogM)O(n⋅m)m 为位数基的形式每个基的最高位唯一但低位可能含其他基位行最简形每个基除最高位外其余位尽量为 0额外功能最大异或和、存在性判断第 k 小异或值需再处理、维数内存占用固定大小数组动态数组三、例题1.题目信息出处2026牛客多校训练营第二场B题难度1876题目描述小羊有一个非负整数列表和两个空的多重集合。他需要将列表中的每个整数放入两个多重集合之一。 注意多重集合可以包含重复的值。 为了给小羊的工作评分他的领导分别计算两个多重集合的按位异或XOR值并将结果相加得 到最终得分。小羊希望最大化得分你能告诉他最高能得多少分吗 一个多重集合的按位异或值为这个集合的异或和。空的多重集合的按位异或值视为0。输入格式每个测试包含多组测试用例。第一行包含测试用例数T1⩽T ⩽104。接下来是每组测试用例的描 述。 每组测试用例的第一行包含一个整数n1⩽n⩽5×105——列表的长度。 每组测试用例的第二行包含n个整数a1,a2,...,an0⩽ai 230——列表中的元素。 保证所有测试用例的n之和不超过5×105。输出格式对于每组测试用例输出一个整数表示最大得分。样例输入4 1 1 3 1 2 3 4 1 1 3 3 4 1 2 2 3输出1 6 6 42.思路推导给定一个非负整数列表需要将其分成两个多重集合 A 和 B设 A 的异或和为 XB 的异或和为 Y所有数的异或和为则有 X⊕YS,目标是最大化 XY。利用恒等式因此最大化 XY 等价于最大化 X∧Y。又因为 YX⊕S所以其中 ∼S 表示对 S 的二进制位取反仅考虑题目给定的位数范围如 30 位通过按位分类讨论不难证明该结论成立。因此问题转化为在所有可能的子集异或和 X 中最大化 X 在 S 为 0 的位上的取值。由于 X 是原数组某个子集的异或和而 X∧(∼S) 相当于先对每个数 ai​ 保留 S 为 0 的位即与 ∼S 做按位与再求子集异或和。因此构造新数组 bi​ai​∧(∼S)则原问题等价于求 bi​ 的所有子集异或的最大值 M。使用线性基可以高效求出 M将所有 bi​ 插入线性基然后查询最大异或值即可。最终答案即为 S2M。3.AC代码#includebits/stdc.h using namespace std; using ll long long; const int N 5e59; int a[N]; class LB { public: const int BASE31; vectorintd; int cnt; LB() { d.resize(BASE1); cnt0; } bool insert(int val) { for(int iBASE-1;i0;--i) { if(val(1lli)) { if(!d[i]) { d[i]val; return 1; } val^d[i]; } } return 0; } int askmax() { int res0; for(int iBASE-1;i0;--i) { if((res^d[i])res)res^d[i]; } return res; } }; void solve() { LB lb; int n; cin n; int xorsum0; for(int i1;in;i) { cin a[i]; xorsum^a[i]; } bitset31bs(xorsum); int bas(~bs).to_ullong(); for(int i1;in;i) { lb.insert(a[i]bas); } cout (ll)(xorsum2ll*(lb.askmax())) \n; } int main() { cin.tie(0)-sync_with_stdio(0); int t; cin t; while(t--)solve(); return 0; }