位运算

基本操作与常用技巧

六种基本位运算：AND（&）、OR（|）、XOR（^）、NOT（~）、左移（<<）、右移（>>）。几个最常用的技巧：

常用技巧速查

// Common bit tricks
int x = 42;
int k = 3;

bool bitK    = (x >> k) & 1;       // check bit k
int  setK    = x | (1 << k);       // set bit k
int  clearK  = x & ~(1 << k);      // clear bit k
int  lowbit  = x & (-x);           // isolate lowest set bit
int  dropLow = x & (x - 1);        // clear lowest set bit
bool isPow2  = x > 0 && !(x & (x-1)); // is power of 2

// Brian Kernighan popcount
int popcount(int n) {
    int cnt = 0;
    while (n) { n &= n - 1; cnt++; }
    return cnt;
}

溢出提示：对 int（32 位）做 1<<31 会触发未定义行为，改用 1LL<<31 或 (unsigned)1<<31。

XOR 性质与应用

XOR 的三个核心性质：① a ^ a = 0；② a ^ 0 = a；③ 满足交换律与结合律。这使得 XOR 天然适合「消去成对元素、找单一元素」类问题。

// LC 136 — Single Number: XOR all, pairs cancel
int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int x : nums) res ^= x;
    return res;
}

// LC 260 — Two numbers appear once
pair<int,int> singleNumberIII(vector<int>& nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;
    int bit = xorAll & (-xorAll); // lowest bit where a != b
    int a = 0;
    for (int x : nums)
        if (x & bit) a ^= x;
    return {a, xorAll ^ a};
}

典型题目

• 136. 只出现一次的数字（全部 XOR，成对抵消，剩余即答案）
• 260. 只出现一次的数字 III（两个单独数字，用 lowbit 分组）
• 137. 只出现一次的数字 II（每个位出现 3 次，取模 3 求单独位）
• 268. 丢失的数字（0..n XOR nums[]，成对抵消）

分组技巧：260 题有两个只出现一次的数 a、b：先全 XOR 得 a^b，取其 lowbit（a 和 b 在该位的值不同），用该位将所有数分为两组，各组 XOR 即得 a 和 b。

位计数

统计一个整数中 1 的个数（popcount）。Brian Kernighan 算法：反复用 x &= (x-1) 消去最低位的 1，循环次数等于 1 的个数。C++20 起可用 __builtin_popcount(x)。

典型题目

• 191. 位 1 的个数（Hamming 重量）
• 338. 比特位计数（0..n 所有数的 popcount，dp: bits[i] = bits[i>>1] + (i&1)）
• 201. 数字范围按位与（找 [m,n] 共同前缀，右移直至 m==n）
• 190. 颠倒二进制位（逐位取并放到对称位置）

内置函数：竞赛/面试中可用 __builtin_popcount(x)（GCC 扩展），std::popcount(x)（C++20），或手写 Brian Kernighan 循环。

位掩码 DP

当 n ≤ 20 时，可用整数的二进制位表示子集状态，枚举所有 2^n 个子集做 DP。枚举子集的子集：for(int sub=mask; sub; sub=(sub-1)&mask)。

典型题目

• 698. 划分为 k 个相等的子集（bitmask + 记忆化）
• 1494. 并行课程 II（拓扑 + 位掩码 DP）
• 847. 访问所有节点的最短路（BFS + 状态 = (当前节点, 已访问集合)）

复杂度：枚举所有子集 O(2^n)，枚举所有子集的子集 O(3^n)（因为每个元素有三种状态：在 mask 中且在 sub 中、在 mask 中且不在 sub 中、不在 mask 中）。