📚 课堂笔记 — 2026年6月22日

🎯 今日专题：位运算

位运算知识树
├── 🔢 基础操作
│   ├── &  按位与
│   ├── |  按位或
│   ├── ^  按位异或
│   ├── ~  取反
│   ├── << 左移
│   └── >> 右移
│
├── 🧩 经典应用
│   ├── 判断2的幂 → n & (n-1) == 0
│   ├── 判断4的幂 → 2的幂 + 偶数位为1
│   ├── 统计1的个数 → n & (n-1) 消最低位1
│   ├── 异或找唯一数 → XOR性质
│   └── 高低位交换 → 移位 + 或运算
│
└── 🚀 进阶技巧
    ├── 逐位统计法 → "只出现一次"通用解法
    └── 位运算化简 → x|y + x&y = x+y

---

1️⃣ 位1的个数 P7379

题意：统计无符号32位整数的二进制中 1 的个数（汉明重量）。

🔑 核心方法：n & (n-1) 消去最低位的1

n     = 1011000
n - 1 = 1010111
n & (n-1) = 1010000   ← 最低位的1消失了！

每次执行 n &= n-1，1的个数减1，循环次数 = 1的个数。

int count = 0;
while (n) {
    n &= n - 1;   // 消去最低位的1
    count++;
}

💡 也可以用 __builtin_popcount(n) 直接求（GCC内置函数）。

---

2️⃣ 2的幂 P7382

题意：判断整数 $n$ 是否是 $2$ 的幂。

🔑 核心判断：n > 0 && (n & (n-1)) == 0

原理：2的幂的二进制只有一个1。

8  = 1000    →  8 & 7 = 1000 & 0111 = 0 ✅
6  = 0110    →  6 & 5 = 0110 & 0101 = 0100 ≠ 0 ❌

if (n > 0 && (n & (n - 1)) == 0) cout << "Yes";
else cout << "No";

⚠️ 必须 n > 0！0 不是任何正整数的幂。

---

3️⃣ 4的幂 P7384

题意：判断 $n$ 是否是 $4$ 的幂。

🔑 两步判断：先判2的幂，再判1在奇数位

原理：4的幂 = 2的偶数次幂，二进制中唯一的1在奇数位（从0开始数）。

4^0 = 1    = 0000...0001  ← 第0位
4^1 = 4    = 0000...0100  ← 第2位
4^2 = 16   = 0001...0000  ← 第4位

掩码 0x55555555 = 0101...0101，只有奇数位为1。

if (n > 0 && (n & (n-1)) == 0 && (n & 0x55555555) != 0)
    cout << "Yes";
else cout << "No";

💡 4的幂 ⊂ 2的幂，所以先过2的幂的门槛，再用掩码筛选。

---

4️⃣ 汉明距离 P7387

题意：两个整数二进制中不同位的个数。

🔑 核心：a ^ b 后统计1的个数

原理：异或 ^ 的性质——相同为0，不同为1。所以 a ^ b 中1的个数就是汉明距离。

int n = a ^ b;    // 不同位变1
int count = 0;
while (n) {
    n &= n - 1;
    count++;
}
cout << count;

🔗 本题 = 异或 + 位1的个数，两道题的组合！

---

5️⃣ 只出现一次的数字 P7380

题意：数组中所有数出现2次，只有一个数出现1次，找出它。

🔑 核心：全部异或

XOR性质：

• a ^ a = 0（自己和自己异或为0）
• a ^ 0 = a（和0异或不变）
• 异或满足交换律和结合律

int ans = 0;
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    ans ^= a[i];   // 成对的数异或后消为0，只剩孤独的数
}
cout << ans;

💡 时间 O(n)，空间 O(1)，比哈希表更优雅！

---

6️⃣ 只出现一次的数字 II P7385

题意：数组中所有数出现3次，只有一个数出现1次。

🔑 核心：逐位统计

原理：对每一个二进制位独立统计1出现的次数，次数 % 3 的余数就是答案在该位的值。

输入：2 2 3 2
二进制：
  2 = 010
  2 = 010
  3 = 011
  2 = 010
─────────────
位统计：第0位有3个1 → 3%3=0
        第1位有4个1 → 4%3=1
        第2位有0个1 → 0%3=0
答案：010 = 2... 不对？答案应该是3！

等等，3=011，第0位1个，第1位4个，第2位0个
→ 1%3=1, 4%3=1, 0%3=0 → 011 = 3 ✅

int bit[35] = {};   // 每一位1的计数
for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    for (int j = 0; x; j++, x >>= 1)
        if (x & 1) bit[j]++;
}
long long ans = 0, pw = 1;
for (int j = 0; j < 35; j++) {
    if (bit[j] % 3) ans += pw;
    pw *= 2;
}
cout << ans;

💡 这是"只出现一次"的通用解法，把3换成任何k都行！

---

7️⃣ 只出现一次的数字 III P7386

题意：数组中所有数出现k次，只有一个数出现1次。

🔑 与第6题完全相同的逐位统计法

唯一区别：bit[j] % k 而不是 bit[j] % 3。

// 和上题一模一样，只需把 %3 改成 %k
if (bit[j] % k != 0) ans += pw;

🎯 模式总结： | 出现次数 | 解法 | |---------|------| | 所有数出现2次 | 全部异或 | | 所有数出现k次 | 逐位统计，count % k |

---

8️⃣ 最大的位运算和 P7381

题意：选两个不同下标的元素，使 (x | y) + (x & y) 最大。

🔑 关键恒等式：x | y + x & y = x + y

证明：对于每一位：

• 如果都是1 → 或=1，与=1，和=2 = 1+1
• 如果一个1一个0 → 或=1，与=0，和=1 = 1+0
• 如果都是0 → 或=0，与=0，和=0 = 0+0

所以 (x|y) + (x&y) = x + y，问题等价于找数组中最大的两个数之和！

sort(a + 1, a + n + 1);
cout << a[n] + a[n - 1];   // 最大的两个数之和

💡 一道看似复杂的位运算题，用恒等式化简后变成了排序！先化简再编码是关键思维。

---

9️⃣ 又一道数组问题 P7222

题意：找最小 $x$（$2 \le x \le 10^{18}$），使数组中存在 $a_i$ 满足 $\gcd(a_i, x) = 1$。

🔑 核心：答案一定是前25个素数之一

原理：要让 $\gcd(a_i, x) = 1$，$x$ 不能和 $a_i$ 共享任何素因子。$x$ 越小越好，而最小的候选就是小素数。

• 如果某个素数 $p$ 不是任何 $a_i$ 的因子，则 $\gcd(a_i, p) = 1$ 对某个 $i$ 成立
• 答案最多到第25个素数（97），因为 $a_i$ 最多只有约15个不同素因子

int primes[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int ans = 1e9;
for (int i = 1; i <= n; i++)
    for (int j = 0; j < 25; j++)
        if (__gcd(a[i], primes[j]) == 1) {
            ans = min(ans, primes[j]);
            break;   // 对每个a_i只需找最小的素数
        }

⚠️ 这道题卡了4次WA（提交5次才AC），可能是因为没考虑到 $a_i$ 可达 $10^{18}$ 需用 long long。

---

🔟 二进制折半交换 P2548

题意：32位无符号整数，高低16位交换。

🔑 核心：左移16位 + 右移16位

原始：[高16位][低16位]
交换：[低16位][高16位]
     = 低16位左移16 + 高16位右移16

unsigned int n;
cin >> n;
cout << (n << 16) + (n >> 16);

💡 注意必须用 unsigned int！有符号数右移是算术右移（补符号位），结果会错。

---

1️⃣1️⃣ 划分苹果 P168

题意：$n$ 个苹果分两堆，使重量差最小。$n \le 20$。

🔑 核心：枚举子集（位掩码）

每个苹果选/不选，用 $n$ 位二进制表示，共 $2^n$ 种方案。

for (int mask = 0; mask < (1 << n); mask++) {
    long long sum = 0;
    for (int j = 0; j < n; j++)
        if ((mask >> j) & 1) sum += a[j];
    ans = min(ans, abs(sum - (total - sum)));
}

💡 $n \le 20$ 时 $2^{20} \approx 10^6$，位掩码枚举完全可行。如果 $n$ 更大则需用 01背包。

---

🧠 位运算核心公式速查

公式	含义	应用
n & (n-1)	消去最低位的1	判2的幂、统计1的个数
n & (-n)	取出最低位的1	树状数组lowbit
a ^ a = 0	自身异或为0	找出现1次的数（其余出现2次）
a ^ 0 = a	与0异或不变	异或的初始化
x | y + x & y = x + y	位运算恒等式	化简位运算表达式
1 << k	第k位设为1	枚举、掩码
(n >> k) & 1	取第k位	逐位统计

---

⚠️ 今日易错点

错误	正确做法
判2的幂忘检查 n > 0	n > 0 && (n & (n-1)) == 0
用 int 处理 $10^{18}$	必须用 long long
有符号数右移	用 unsigned int 做逻辑右移
n & 1 > 0 的优先级	应写 (n & 1) > 0（> 优先级高于 &）
4的幂只判2的幂	还需检查1在奇数位 (n & 0x55555555) != 0
"只出现一次"暴力哈希	出现k次时用逐位统计法更通用

---

📈 学习曲线

17:52 ━▶ 位1的个数 ✅（位运算入门）
18:06 ━▶ 2的幂 ✅（n & (n-1) 技巧）
18:16 ━▶ 4的幂 ✅（掩码筛选）
18:17 ━▶ 汉明距离 ✅（异或 + 统计1）
18:23 ━▶ 二进制折半交换 ✅（移位操作）
18:30 ━▶ 只出现一次 ✅（XOR性质）
18:57 ━▶ 只出现一次II ✅（逐位统计）
19:08 ━▶ 只出现一次III ✅（逐位统计推广）
19:09 ━▶ 最大位运算和 ✅（恒等式化简）
19:16 ━▶ 又一道数组问题 ✅（GCD+素数枚举）
19:37 ━▶ 划分苹果 ✅（位掩码枚举子集）

🔑 今日核心收获：掌握了位运算的三大经典套路——消1判幂、异或去重、逐位统计。位运算不仅是技巧，更是一种从二进制视角思考问题的方法。

---