illegalCreed

中文

English

中文

English

Appearance

经典应用与位掩码 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 只出现一次的数字：数组里除一个数出现一次外其余都出现两次——全部异或起来，成对的抵消（a^a=0），剩下就是那个单数。O(n) 时间 O(1) 空间。
  • 不用加减法求和：a + b = (a ^ b) + ((a & b) << 1)——异或是无进位和，与左移是进位，循环把进位加回去直到进位为 0。模拟了硬件加法器。
  • 汉明重量（popcount）：二进制中 1 的个数——n &= n-1 每次抹一个 1，数循环次数；或查表、内置 __builtin_popcount。
  • 汉明距离：两数二进制不同位的个数——先 a ^ b（不同位变 1），再求汉明重量。
  • 状态压缩 DP：用整数的每一位表示一个元素选/不选，把 O(2^n) 的子集枚举压成一个数遍历——旅行商、子集划分、数位 DP 的核心。
  • 枚举子集：for (let sub = mask; sub > 0; sub = (sub - 1) & mask)——按降序枚举 mask 的所有非空子集，O(3^n) 枚举所有子集的子集。
  • 权限标志位：读写执行用不同位（读=4=0b100、写=2=0b010、执行=1=0b001），用或授权、与检测、异或撤销——Unix 文件权限 rwxr-xr-x 即此。
  • 位运算优化常数：把 % 2、/ 2、* 2 换成 & 1、>> 1、<< 1——现代编译器常自动优化，但热路径手写仍有意义。
  • 复杂度：只出现一次的数字 O(n)、不用加减法求和 O(位数) = O(log max)、汉明重量 O(位数)、状态压缩 DP O(2^n × n)。

一、只出现一次的数字：异或的成对抵消 ​

给定数组，除一个元素出现一次外，其余都出现两次，找那个单数（LeetCode 136）。

原理：异或的自反性 a ^ a = 0 和恒等性 a ^ 0 = a——把所有数异或起来，出现两次的成对抵消成 0，最后剩下出现一次的那个。

js
function singleNumber(nums) {
  let ans = 0;
  for (const x of nums) ans ^= x;   // 0 ^ x = x，成对抵消
  return ans;
}
  • 为什么 ans 初值是 0：0 ^ x = x，从 0 开始异或等价于直接累乘异或。
  • 扩展：其余出现三次，找出现一次的那个（LeetCode 137）：不能直接异或（三次不抵消）。思路是「按位统计每个二进制位上 1 出现的总次数，对 3 取模」，余数就是单数那一位的值——这是「数位 DP / 状态机」解法。
  • 哈希表 vs 位运算：哈希表 O(n) 时间 O(n) 空间；异或 O(n) 时间 O(1) 空间——位运算省了空间，是空间最优解。

二、不用加减法求和：模拟硬件加法器 ​

不使用 +、-，求两整数之和（LeetCode 371）。核心是把加法拆成「无进位和」与「进位」两部分，循环直到没有进位。

原理：观察二进制加法的逐位结果——

  • 无进位和 = a ^ b（异或的真值表 0+0=0, 0+1=1, 1+0=1, 1+1=0(进位) 与逐位和无进位完全一致）。
  • 进位 = (a & b) << 1（两数都为 1 才产生进位，且进位贡献到高一位）。

把「无进位和」与「进位」再相加（递归/循环），直到进位为 0。

js
function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1;   // 进位（注意 JS 要用无符号处理大数）
    a = a ^ b;                    // 无进位和
    b = carry;                    // 把进位加回去
  }
  return a;
}
  • 终止条件：b === 0（没有进位了），此时 a 就是最终和。
  • 为什么能终止：每轮进位 carry 左移一位，最高位的进位最终移出（32 位下最多 32 轮），必然归零。
  • JS 的坑：a & b 在 JS 里是 32 位有符号运算，<< 1 可能把符号位移出变负数——处理大正数（>2³⁰）时要用 >>> 0 转无符号或用 Math.clz32 辅助。Python 无此问题（任意精度）。

三、汉明重量与汉明距离 ​

汉明重量（Hamming Weight / popcount）：一个数二进制中 1 的个数。

js
// 方法 1：n & (n-1) 抹 1 法（只循环 1 的个数次）
function hammingWeight(n) {
  let c = 0;
  while (n !== 0) { n &= n - 1; c++; }
  return c;
}

// 方法 2：查表法（每 8 位查一次预计算的 1 的个数表）
const POPCNT = [/* 0~255 各值的 1 的个数 */];
function popcount(n) {
  let c = 0;
  while (n !== 0) { c += POPCNT[n & 0xff]; n >>>= 8; }
  return c;
}

汉明距离（Hamming Distance）：两数二进制不同位的个数——先异或（不同位变 1），再求汉明重量。

js
function hammingDistance(x, y) {
  return hammingWeight(x ^ y);   // 异或后数 1
}
  • 内置函数：C++ __builtin_popcount、Java Integer.bitCount、Python bin(x).count('1') 或 int.bit_count()（3.10+）、JS Math 无原生但 x.toString(2).split('1').length - 1 可凑。
  • LeetCode 461 汉明距离 就是这套路的直接应用。

四、状态压缩：用整数表示集合 ​

当集合元素数 n 较小（≤ 20，因为 2²⁰ ≈ 10⁶ 可接受），可以用一个整数的每一位表示一个元素的「选/不选」，把集合压成一个数（位掩码）。

位掩码语义：整数 mask 的第 i 位为 1 表示元素 i 在集合里，为 0 表示不在。

js
// 集合操作
const has     = (mask, i) => (mask >> i) & 1;          // 查 i 是否在集合
const add     = (mask, i) => mask | (1 << i);          // 加入 i
const remove  = (mask, i) => mask & ~(1 << i);         // 移除 i
const size    = (mask) => hammingWeight(mask);          // 集合大小
const isFull  = (mask, n) => mask === (1 << n) - 1;    // 是否全集

枚举子集（位运算 DP 高频模板）：枚举 mask 的所有非空子集，sub 按降序变化：

js
for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
  // sub 依次是 mask 的每个非空子集（降序）
}
  • 为什么 (sub-1) & mask 是下一个更小子集：sub-1 会把 sub 最低位的 1 借位变 0、低位全变 1，再与 mask 相与把超出 mask 的位清掉——正好跳到下一个属于 mask 的更小子集。
  • 复杂度：枚举一个 mask 的所有子集是 O(2^popcount(mask))；枚举所有 mask 的所有子集总和是 O(3^n)。

状态压缩 DP 应用：旅行商问题（TSP，dp[mask][i] = 访问了 mask 集合、最后在 i 的最短路径）、划分等和子集、数位 DP。详见动态规划进阶 叶。

五、权限标志位：读写执行 ​

Unix 文件权限 rwxr-xr-x（755）就是位掩码的经典应用：用 3 位表示读（4 = 0b100）、写（2 = 0b010）、执行（1 = 0b001），或起来得到一个 0~7 的权限值。

js
const READ = 4, WRITE = 2, EXEC = 1;   // 0b100, 0b010, 0b001

// 授权（或）
let perm = 0;
perm |= READ | WRITE;        // 读写权限 = 6 = 0b110

// 检测（与）
const canRead  = (perm & READ)  !== 0;   // true
const canExec  = (perm & EXEC)  !== 0;   // false

// 撤销（异或或与非）
perm &= ~WRITE;              // 撤销写权限 = 4 = 0b100
perm ^= READ;                // 翻转读权限 = 0 = 0b000
  • 为什么权限位用 2 的幂：每个权限独占一位，互不干扰——授权用或（叠加）、检测用与（掩码）、撤销用与非。这是「多个布尔标志压成一个整数」的通用模式。
  • 工程应用：Linux 文件权限、HTTP 状态码分类、特性开关（feature flags）、数据库权限字段、HTML 元素的 disabled/readonly 多状态——都用这种「位掩码」思想。

六、位运算优化性能 ​

在性能敏感的热路径，把算术/条件换位运算可减少分支、缩短指令：

  • x % 2 → x & 1、x * 2 → x << 1、x / 2 → x >> 1：现代编译器（GCC -O2、V8）常自动做这些优化，手写不一定更快，但语义更明确时可用。
  • 用位运算避免分支：x === 0 ? 0 : y 在某些场景可写成 (x !== 0) * y 或位运算变体，避免分支预测失败（但可读性差，慎用）。
  • 位运算哈希/压缩：n & (capacity - 1) 代替 n % capacity（当 capacity 是 2 的幂时等价且快）——这是哈希表（HashMap）求桶下标的标准技巧。

注意：不要为了「看起来高级」滥用位运算——现代编译器的优化能力很强，普通算术写法往往已生成最优代码，且可读性好得多。位运算优化应基于实测 profiling，而非主观臆断。

下一步 ​

位运算叶到此完成。位运算思想最优雅的应用是快速幂——用「把指数按二进制拆位 + 逐位判断」把 O(n) 幂运算降到 O(log n)，建议结合快速幂理解位运算如何驱动分治优化。