干净又实用的位运算备忘——涵盖位操作的语义、若干常用恒等式与经典技巧（含代码示例和注意事项）。适合刷题/写底层代码/竞赛时速查。

基础语义（按位操作）

  • &：按位与（AND）。1&1=1，其余为0。用于掩码（mask）/清位。
  • |：按位或（OR）。至少有1则为1。用于置位/合并标志。
  • ^：按位异或（XOR）。相同为0，不同为1。用于无进位加法、交换两个数、不重复元素。
  • ~：按位取反（NOT）。~x = 按位翻转（注意有符号整型含符号位）。
  • <<：左移（乘2的幂，低位补0）。
  • >>：右移（逻辑/算术取决于语言/类型，注意符号扩展）。
  • -n：负数（在二进制中通常以 二补码 表示），性质：-n = ~n + 1。

二进制与二补码（关键恒等）

  • 负数表示（两补）：-n == (~n) + 1。
    例：若 n = 5 (00000101)，则 -n = 11111011（8位表示）。
  • n & (n - 1)：清除最低位的 1（把 n 的最低位1置为0）
    证明直观：n-1 把最低 1 变 0，并把其右边的 0/1 翻转，因此与操作清掉那个 1。
    用途：计数二进制 1 的个数（见下）。
  • n & (-n)：提取最低位的 1（最低位 1 的掩码）
    例：n = 12 (1100) -> n & -n = 0100 (4)。
  • n ^ (n - 1)：最低位 1 及其右边全部变成 1（形如 ...00111...）。常用来构造掩码。
  • ~n 与 -n 的组合常用于位运算构造或取反掩码：清第 k 位：n & ~(1<<k)。

经典技巧与代码（C / C++ / Python 表示）

1) 判断是否为 2 的幂

bool isPow2(unsigned n) {
    return n &amp;&amp; !(n &amp; (n - 1));
}

（零不是幂；n & (n-1) == 0 当且仅当 n 是 2 的幂）

2) 计数二进制 1（Brian Kernighan 算法）

int popcount(unsigned n) {
    int cnt = 0;
    while (n) {
        n &amp;= (n - 1); // 清掉最低位的 1
        cnt++;
    }
    return cnt;
}

3) 提取最低位的 1

unsigned lowbit(unsigned n) {
    return n &amp; -n; // 等价于 n &amp; (~n + 1)
}

4) 清掉最低位的 1（得到 n 的下一个子集）

unsigned remove_lowest_one(unsigned n) {
    return n &amp; (n - 1);
}

5) 枚举一个集合的所有非空子集（位掩码技巧）

// 遍历 s 的所有子集 t (包括空集，若要排除空集可处理)
for (unsigned t = s; t; t = (t - 1) &amp; s) {
    // 处理子集 t
}

6) 交换两个整数（无临时变量，用 XOR）

a ^= b;
b ^= a;
a ^= b;

（仅当 a 与 b 不是同一地址时安全；否则会变 0）

7) 设置 / 清除 / 切换 / 读取第 k 位

// set k-th bit
n |= (1u &lt;&lt; k);

// clear k-th bit
n &amp;= ~(1u &lt;&lt; k);

// toggle k-th bit
n ^= (1u &lt;&lt; k);

// get k-th bit (0/1)
int bit = (n >> k) &amp; 1;

8) 构造从 0 到 k 连续的低位掩码

// mask with lowest k bits set: (1&lt;&lt;k) - 1
unsigned mask = (1u &lt;&lt; k) - 1;  // 当 k==32 要小心溢出（使用 64 位）

9) 判断两个数是否异号（常用于溢出检测）

bool diff_sign(int x, int y) {
    return (x ^ y) &lt; 0;
}

（最高位不同则异号）

10) 向上/向下对齐到 2 的幂（对齐常见）

// 向上对齐 x 到 2^k（假设 x>0 且 k 是幂）
unsigned align_up(unsigned x, unsigned a) {
    return (x + a - 1) &amp; ~(a - 1); // a 必须是幂
}

常见题型与位运算解法思路（刷题指南）

  • 找出只出现一次/两次/三次的数：使用 XOR / 位按位统计（对每一位计数 mod k）。
  • 子集枚举与状态压缩 DP：位掩码遍历、子集转移常用 (s & -s)、s & (s-1)。
  • 最低位相关操作：n & -n、n & (n-1) 是常见 O(1) 小技巧。
  • 位 DP 中使用 popcount(mask) 或预计算 __builtin_popcount（GCC/Clang）加速状态代价计算。

注意事项与陷阱

  1. 有符号右移：>> 对有符号类型通常是算术右移（保持符号），对无符号则做逻辑右移。题目中若依赖位模式，建议使用 unsigned。
  2. 优先级：位运算优先级低于加减、移位高于比较等；用括号避免歧义：n & (n - 1)。
  3. 溢出/类型宽度：1 << 31 在 32 位 int 上可能是 UB/移位边界；尽量使用 1u 或更宽类型 1ULL。
  4. XOR 交换的局限：当 a 和 b 指向同一内存（例如同一个变量的别名）时会出错；也会降低可读性，现代编译器优化下用临时变量更清晰。
  5. ~ 运算与负数：~n 与 -n 都依赖位宽，注意在打印/比较时与有符号/无符号的差别。

小结（记住这几条）

  • -n = ~n + 1（两补码）
  • n & (n - 1) —— 清最低位 1
  • n & -n —— 提取最低位 1（最低 1 的掩码）
  • n && !(n & (n - 1)) —— 判断是否为 2 的幂
  • 枚举子集：for (t = s; t; t = (t - 1) & s)
  • 位运算适合：计数、掩码、状态压缩、加速常数操作