讲解

位运算直接操作整数的二进制位：与 &、或 |、异或 ^、取反 ~、左移 <<、右移 >>。它在算法题中的角色是「巧劲」：很多题用位运算能把 O(n) 空间降到 O(1)，或把枚举代码压缩成一行。位运算题目占比不大，但出现的几乎都是套路题，记住几个固定招式即可稳拿。

第一招：异或的三条性质——x ^ x = 0、x ^ 0 = x、异或满足交换律结合律。「只出现一次的数字」（其他都出现两次）把全数组异或一遍，成对的互相抵消，剩下的就是落单者：O(n) 时间 O(1) 空间，任何哈希表解法在常数空间要求面前都要让位。扩展版（两个落单者）先全异或得到 a^b，再取最低位的 1 把数组分成两组分别异或——思路同构。

第二招：n & (n - 1) 消去最低位的 1。数一个数有多少个 1 位（汉明重量），循环「消一个、数一个」，次数正好等于 1 的个数，比逐位检查快；顺带得到判断 2 的幂的一行式：n > 0 且 n & (n-1) === 0（2 的幂的二进制只有一个 1）。第三招：用整数的二进制位枚举子集——n 个元素对应 [0, 2ⁿ) 的每个整数，第 i 位为 1 表示选第 i 个元素，2ⁿ 个子集一次双重循环全部生成。这是回溯「选 / 不选」模型的位运算版本，n 小（<= 20）时写起来比递归还快。

示例

三招全演示：异或找落单者、n & (n-1) 数 1 与判 2 的幂、二进制掩码枚举子集：

import assert from 'node:assert/strict';

function singleNumber(nums) {
  let result = 0;
  for (const x of nums) result ^= x; // 成对抵消
  return result;
}

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1; // 消去最低位的 1
    count++;
  }
  return count;
}

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

// 掩码 mask 的第 i 位为 1 表示选 nums[i]
function subsetsByBits(nums) {
  const n = nums.length;
  const result = [];
  for (let mask = 0; mask < 1 << n; mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if ((mask >> i) & 1) subset.push(nums[i]);
    }
    result.push(subset);
  }
  return result;
}

assert.strictEqual(singleNumber([2, 2, 1]), 1);
assert.strictEqual(singleNumber([4, 1, 2, 1, 2]), 4);

assert.strictEqual(hammingWeight(11), 3); // 1011
assert.strictEqual(hammingWeight(128), 1); // 10000000
assert.ok(isPowerOfTwo(16));
assert.ok(!isPowerOfTwo(18));
assert.ok(!isPowerOfTwo(0));

const subs = subsetsByBits([1, 2, 3]);
assert.strictEqual(subs.length, 8); // 2^3
assert.ok(subs.some((s) => s.length === 0)); // 空集在内
assert.deepStrictEqual(subs[0b101], [1, 3]); // mask 5 = 选第 0、2 个

assert.strictEqual(1 << 10, 1024); // 左移 n 位 = 乘 2^n
console.log('位运算示例全部通过');

subs[0b101] 这一断言演示了掩码的阅读方式：二进制 101 表示「选第 0 位和第 2 位元素」，即 [1, 3]。会用 0b 字面量读写掩码，位运算代码就从天书变成了表格。

常见坑

  • JS 位运算的 32 位截断：JS 数字是 64 位浮点，但位运算先截成 32 位有符号整数——超过 2³¹ 的数做位运算会出错，大数场景换 BigInt。
  • 右移用 >>> 和 >> 不分：>> 是算术右移（负数补 1），>>> 是无符号右移（补 0）；处理「无符号 32 位」题意时用 >>>，日常正数两者相同。
  • 异或找落单者用在出现三次的题上：「其他出现三次」要换按位计数（每一位上的 1 数 mod 3）或状态机，异或只对「两次」有效。
  • 掩码枚举办数爆炸：2ⁿ 个子集，n 超过 25 基本不可行；位运算子集是 n 小场景的速写工具，不是通用替代。
  • 运算优先级坑：==、!= 优先级高于 &、|，位运算表达式务必加括号：(mask >> i) & 1 而不是 mask >> i & 1。

小结

位运算三招：异或消对（x^x=0）、n&(n-1) 消最低位 1、二进制掩码枚举子集；注意 JS 位运算的 32 位截断和运算优先级。最后一章收束全教程：刷题方法与面试策略。