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

一、位运算公式及证明

1.公式概览

2.公式详细证明

i. 加法公式：a+b=a⊕b+2×(a&b)

证明：

二进制加法中，每一位的计算分为两步：

• 本位和（不进位）：等于两个比特的异或结果 ai​⊕bi​。

• 进位：只有当两个比特都是1时才产生进位，即 ai​&bi​，并且这个进位要加到高一位上，相当于左移一位，即乘以2。

将所有位求和：

a+b=∑(ai​⊕bi​)⋅2i+∑(ai​&bi​)⋅2i+1=(a⊕b)+2×(a&b)

举例：a=5(101),b=3(011)

• a⊕b=110=6

• a&b=001=1

• 6+2×1=8，与 5+3=8 一致。

ii. 减法公式：a−b=a⊕b−2×(∼a&b)

证明：

减法中的借位发生在 ai​=0,bi​=1 的位上，即 ∼ai​&bi​。借位会向高位传播，相当于从高位减去 2i+1。

因此：

a−b=(a⊕b)−2×(∼a&b)

举例：a=5(101),b=3(011)

• a⊕b=110=6

• ∼a=010，∼a&b=010=2

• 6−2×2=2，与 5−3=2 一致。

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

证明：

设初始 a=x,b=y。

• 第一步：a=x⊕y

• 第二步：b=a⊕y=(x⊕y)⊕y=x⊕(y⊕y)=x⊕0=x

• 第三步：a=a⊕b=(x⊕y)⊕x=y⊕(x⊕x)=y⊕0=y

  最终 a=y,b=x。

  依赖性质：异或满足交换律、结合律，且 x⊕x=0，x⊕0=x。

v. 求绝对值：mask = x >> 31; return (x ^ mask) - mask;

证明：

• 若 x≥0：mask = 0，(x ^ 0) - 0 = x，正确。

• 若 x<0：mask = -1（全1），x ^ (-1) = \sim x（按位取反），再减去 (−1) 即加1，得到 ∼x+1。这正是负数的补码绝对值（取反加一）。

  因此结果总是 ∣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。

  加上 n>0 排除0的情况（0不是2的幂，且 0&(−1)=0 会误判）。

vii. 清除最低位1：n & (n-1)

证明：

设 n 的最低位的1在第 k 位（从0开始），即 n 的二进制为...100...0（k个0）。

则 n−1 为...011...1（k个1）。

按位与后，第 k 位：1&0=0；更高位不变；更低位的0与1得0。

因此结果比 n 少了那个最低位的1，其余位不变。

举例：n=12(1100)，n−1=11(1011)，1100&1011=1000=8。

viii. 提取最低位1（lowbit）：n & (-n)

证明：

在补码中，−n=∼n+1。

设 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。

举例：n=12(1100)，−12 的补码（8位）为11110100，但低4位为0100，1100&0100=0100=4。

3.基础概念详解

i. 什么是补码？

计算机用固定位数存储整数，为了表示负数，引入了补码系统。

• 正数：原码即其二进制表示，最高位为0。

• 负数：其绝对值的补数，即 2n−∣负数∣（n为位数）。

  简便计算：取反加一。例如求 −5 的8位补码：

  • 5的二进制：00000101

  • 取反：11111010

  • 加1：11111011← 这就是 −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。

• 若 x<0，最高位为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：

1. 从高到低遍历每一位（如 63 → 0）。

2. 若x的第i位为 1：

   • 如果basis[i]不存在，则将x存入basis[i]，结束插入。

   • 否则令x ^= basis[i]，继续向下消去。

3. 最终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() { vector<ll> 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）。具体步骤：

1. 对每一列（从高位到低位）寻找主元。

2. 若找到非零行，交换到当前行，并用它消去下方所有行的该位。

3. 最后，所有非零行就是一组线性基，且它们是两两正交（最高位唯一）的简化形式。

相比普通消元，高斯消元会重新排列基的顺序，并将每个基向量除了最高位外其他位也尽量消干净，得到更规整的基（例如用于求第 k 小异或值时更方便）。

特点

• 时间复杂度 O(n⋅m)，m 为位数（常数）。

• 适用于离线处理，一次性给出所有数。

• 结果可用于求第 k 小异或值、线性空间的维数等。

C++ 代码（高斯消元构造）

#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXB = 60; struct GaussBasis { vector<ll> basis; // 存储行最简形基向量 // 对所有数执行高斯消元 void build(const vector<ll>& nums) { vector<ll> 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() { vector<ll> 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 << bitset<4>(v) << " "; // 1011 (11), 0100 (4) } cout << endl; return 0; }

3.两种构造方式的对比

三、例题

1.题目信息

出处：

2026牛客多校训练营第二场，B题（难度1876）

题目描述：

小羊有一个非负整数列表和两个空的多重集合。他需要将列表中的每个整数放入两个多重集合之一。 注意，多重集合可以包含重复的值。 为了给小羊的工作评分，他的领导分别计算两个多重集合的按位异或（XOR）值，并将结果相加得 到最终得分。小羊希望最大化得分，你能告诉他最高能得多少分吗？ 一个多重集合的按位异或值为这个集合的异或和。空的多重集合的按位异或值视为0。

输入格式：

每个测试包含多组测试用例。第一行包含测试用例数T（1⩽T ⩽104）。接下来是每组测试用例的描 述。 每组测试用例的第一行包含一个整数n（1⩽n⩽5×105）——列表的长度。 每组测试用例的第二行包含n个整数a1,a2,...,an（0⩽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 4

2.思路推导：

给定一个非负整数列表，需要将其分成两个多重集合 A 和 B，设 A 的异或和为 X，B 的异或和为 Y，所有数的异或和为

则有 X⊕Y=S,目标是最大化 X+Y。

利用恒等式

因此最大化 X+Y 等价于最大化 X∧Y。

又因为 Y=X⊕S，所以

其中 ∼S 表示对 S 的二进制位取反（仅考虑题目给定的位数范围，如 30 位），通过按位分类讨论不难证明该结论成立。因此问题转化为：在所有可能的子集异或和 X 中，最大化 X 在 S 为 0 的位上的取值。

由于 X 是原数组某个子集的异或和，而 X∧(∼S) 相当于先对每个数 ai​ 保留 S 为 0 的位（即与 ∼S 做按位与），再求子集异或和。因此构造新数组 bi​=ai​∧(∼S)，则原问题等价于求 bi​ 的所有子集异或的最大值 M。

使用线性基可以高效求出 M：将所有 bi​ 插入线性基，然后查询最大异或值即可。最终答案即为 S+2M。

3.AC代码

#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 5e5+9; int a[N]; class LB { public: const int BASE=31; vector<int>d; int cnt; LB() { d.resize(BASE+1); cnt=0; } bool insert(int val) { for(int i=BASE-1;i>=0;--i) { if(val&(1ll<<i)) { if(!d[i]) { d[i]=val; return 1; } val^=d[i]; } } return 0; } int askmax() { int res=0; for(int i=BASE-1;i>=0;--i) { if((res^d[i])>res)res^=d[i]; } return res; } }; void solve() { LB lb; int n; cin >> n; int xorsum=0; for(int i=1;i<=n;++i) { cin >> a[i]; xorsum^=a[i]; } bitset<31>bs(xorsum); int bas=(~bs).to_ullong(); for(int i=1;i<=n;++i) { lb.insert(a[i]&bas); } cout << (ll)(xorsum+2ll*(lb.askmax())) << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int t; cin >> t; while(t--)solve(); return 0; }