位运算

位运算#

位运算是 \(O(1)\) 的底层操作，常数极小，常被单列为专题 （基础/性质/拆位/试填/恒等式/思维），常用于优化枚举、状态压缩（DP 的 mask）与按位统计。

一、基础操作#

运算

符号

说明

例子

与

&

同 1 才 1，可清位/取交集

x & 1 判断奇偶

或

|

有 1 即 1，可置位/取并集

x | 1 把最低位变 1

异或

^

不同为 1，可翻转/去重

x ^ 1 翻转最低位

取反

~

按位取反

~x = -x - 1

左移

<<

乘 \(2^k\)

1 << k 表示第 k 位

右移

>>

整除 \(2^k\)

x >> k & 1 取第 k 位

异或恒等式（”恒等式”专题核心）：

\[ x \oplus x = 0, \quad x \oplus 0 = x, \quad x \oplus y = y \oplus x, \quad (x \oplus y) \oplus z = x \oplus (y \oplus z) \]

利用 x^x=0 可以 \(O(n)\) 找出只出现一次的元素（其余均出现两次）。

二、常用技巧#

// lowbit：取 x 最低位的 1（树状数组、枚举二进制位的基础）
int lowbit(int x) {
    return x & -x;
}

// 判断第 k 位是否为 1（k 从 0 开始）
bool getBit(int x, int k) {
    return (x >> k) & 1;
}

// 置位 / 清位 / 翻转第 k 位
int setBit(int x, int k) {
    return x | (1 << k);
}
int clearBit(int x, int k) {
    return x & ~(1 << k);
}
int flipBit(int x, int k) {
    return x ^ (1 << k);
}

// 统计二进制中 1 的个数（内置函数更快）
int popcount(int x) {
    return __builtin_popcount(x);
} // Java: Integer.bitCount(x)

Note

判断 x 是否为 2 的幂：x > 0 && (x & (x - 1)) == 0。 判断 x 是否整除 2^k：(x & ((1 << k) - 1)) == 0。

三、枚举子集 / 状态压缩#

用一个整数的二进制位表示集合：第 k 位为 1 表示元素 k 被选中（状压 DP 的基础）。

int n = 5;
// 枚举所有子集（0 ~ 2^n-1）
for (int mask = 0; mask < (1 << n); mask++) {
    // 处理子集 mask
}

// 枚举一个集合 mask 的所有非空子集（经典模板：不断减 lowbit）
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // 处理子集 sub
}

四、拆位（按位统计）#

对每位独立统计贡献，常用于”数组中所有数两两异或之和”类问题：

// 统计数组所有元素在每一位上 1 的个数，再按位计算贡献
long long xorSum(vector<int>& nums) {
    long long ans = 0;
    for (int k = 0; k < 31; k++) {
        long long cnt1 = 0;
        for (int x : nums)
            if ((x >> k) & 1) cnt1++;
        long long cnt0  = nums.size() - cnt1;
        ans            += cnt1 * cnt0 * (1LL << k); // 该位对异或和的贡献
    }
    return ans;
}

Note

拆位的本质是把”按值计算”拆成”按二进制位独立计算”，配合异或/与/或的性质可把复杂度从 \(O(n^2)\) 降到 \(O(n \cdot 31)\)。

Contents