illegalCreed

中文

English

中文

English

Appearance

参考：位运算 API、技巧与应用速查 ​

基于通用算法概念 · 核于 2026-07

速查 ​

  • 六运算：与 &（同 1 才 1）、或 |（有 1 即 1）、非 ~（取反）、异或 ^（不同为 1）、左移 <<（×2^k）、右移 >>（÷2^k，正数补 0 负数补 1）——全部 O(1) 按位独立。
  • 异或性质：自反 a^a=0、恒等 a^0=a、交换结合——成对抵消、交换、无进位加法的根基。
  • 判断奇偶：(n & 1) === 0 偶、=== 1 奇（必须加括号，& 优先级低于 ===）。
  • 去最低位 1：n & (n - 1)——统计 1 个数、判断 2 的幂核心。
  • 取最低位 1（lowbit）：n & (-n)——树状数组基石。
  • 判断 2 的幂：n > 0 && (n & (n - 1)) === 0。
  • 取/设/清/翻第 k 位：(n>>k)&1 / n|(1<<k) / n&~(1<<k) / n^(1<<k)。
  • 不用临时变量交换：a^=b;b^=a;a^=b（要求 a、b 不同地址）。
  • 不用加减法求和：a^b（无进位和）+ (a&b)<<1（进位），循环到进位为 0。
  • 只出现一次的数字：全部异或，成对抵消剩单数，O(n) O(1)。
  • 汉明重量：while(n){n&=n-1;c++;}；汉明距离 = popcount(a^b)。
  • 枚举子集：for(sub=mask;sub>0;sub=(sub-1)&mask)——状态压缩 DP 核心。
  • 易错：优先级（必须加括号）、JS 32 位有符号截断、负数算术右移、-INT_MIN 溢出。
  • 进阶：状态压缩 DP → 动态规划进阶；树状数组（用 lowbit）→ 线段树与树状数组；快速幂 → 快速幂。

一、六种位运算速查表 ​

运算符号规则典型用途示例（a=12, b=10）
与 AND&同 1 才 1遮罩、清零、检测12 & 10 = 8
或 OR|有 1 即 1置位、授权、合并12 | 10 = 14
非 NOT~按位取反构造反向掩码~12 = -13
异或 XOR^不同为 1翻转、抵消、交换12 ^ 10 = 6
左移<<高位补 0乘 2^k、构造掩码12 << 1 = 24
右移>>正补 0 负补 1除 2^k、取位12 >> 1 = 6

三种位运算的用途口诀：与（&）遮罩清零、或（|）置位合并、异或（^）翻转抵消。

二、常用技巧清单 ​

技巧表达式说明
判断奇偶(n & 1) === 0最低位 0 偶 1 奇
去最低位 1n & (n - 1)抹掉最低位的 1
取最低位 1（lowbit）n & (-n)只留最低位的 1
判断 2 的幂n > 0 && (n & (n-1)) === 0仅一个 1
取第 k 位(n >> k) & 1右移再 &1
置第 k 位n | (1 << k)或掩码
清第 k 位n & ~(1 << k)与反向掩码
翻转第 k 位n ^ (1 << k)异或掩码
不用临时变量交换a^=b;b^=a;a^=b异或自反性
异或消除成对reduce(xor)找单元素
统计 1 的个数while(n){n&=n-1;c++}汉明重量

三、经典题代码 ​

只出现一次的数字（LeetCode 136） ​

js
function singleNumber(nums) {
  let ans = 0;
  for (const x of nums) ans ^= x;   // 成对抵消，剩单数
  return ans;
}

不用加减法求和（LeetCode 371） ​

js
function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1;     // 进位
    a = a ^ b;                      // 无进位和
    b = carry;
  }
  return a;                         // 进位为 0 时 a 即和
}

汉明重量 / 汉明距离（LeetCode 191 / 461） ​

js
function hammingWeight(n) {         // 1 的个数
  let c = 0;
  while (n !== 0) { n &= n - 1; c++; }
  return c;
}
function hammingDistance(x, y) {    // 不同位的个数
  return hammingWeight(x ^ y);
}

枚举子集（状态压缩 DP 模板） ​

js
for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
  // sub 降序遍历 mask 的所有非空子集
}

权限标志位 ​

js
const READ = 4, WRITE = 2, EXEC = 1;        // 0b100, 0b010, 0b001
let perm = READ | WRITE;                     // 授权 = 6
const canRead = (perm & READ) !== 0;         // 检测 = true
perm &= ~WRITE;                              // 撤销 = 4

四、异或的代数性质与推论 ​

性质等式应用
自反性a ^ a = 0成对抵消、交换
恒等性a ^ 0 = a异或初值取 0
交换律a ^ b = b ^ a顺序无关
结合律(a^b)^c = a^(b^c)任意分组
异或全 1 = 取反a ^ (-1) = ~a-1 是全 1
无进位加法a ^ b = 无进位的逐位和不用加减求和

记忆：异或 = 「不同为 1」=「不进位加法」——这两句话解释了它的全部用途（抵消、翻转、求和无进位）。

五、补码关键事实 ​

事实说明
-n = ~n + 1补码定义（丢弃溢出位）
-1 = 全 132 位下 0xFFFFFFFF
n & (-1) = n与全 1 不变
n | (-1) = -1或全 1 得全 1
n ^ (-1) = ~n异或全 1 = 取反
范围n 位补码：-2^(n-1) 到 2^(n-1)-1
-INT_MIN = INT_MIN最小负数无对应正数，取反溢出

六、各语言位运算注意点 ​

语言位运算位宽注意点
C/C++int 通常 32 位有符号 >> 算术右移；-INT_MIN UB
Javaint 32 位、long 64 位>>> 无符号右移；Integer.bitCount
JavaScript32 位有符号（ToInt32）大数被截断；~5=-6；>>> 无符号右移
Python任意精度无溢出；-5 是真负数；int.bit_count()（3.10+）
Goint 平台相关无 ~（用 ^ 一元表示取反）；uint 无符号

七、易错点清单 ​

  • 优先级坑（最高频）：& | ^ << >> 优先级低于 == < > 也低于 + -——n & 1 == 0 实际是 n & (1==0) = n & 0 = 0（永远 falsy）。永远加括号：(n & 1) === 0。
  • JS 32 位截断：(2 ** 32) | 0 === 0、(1 << 31) === -2147483648（符号位被置 1）——大数位运算用 BigInt（但 BigInt 不支持 ~、<<）。
  • ~ 结果为负：~5 === -6（不是 4294967290），因为 JS 位运算返回有符号 32 位整数。
  • 算术右移 vs 逻辑右移：>> 对负数补 1（算术），>>>（JS/Java）补 0（逻辑）——处理无符号位图时用 >>>。
  • -n 的溢出：最小负数 -2^31 取相反数等于自身（溢出），lowbit(INT_MIN) 等技巧在边界值上要小心。
  • 不用临时变量交换同地址：a[i] ^= a[i]（i===j）会变 0——先判 i !== j。
  • 判断 2 的幂漏判 n > 0：0 & -1 === 0 会误判 0 为 2 的幂；负数也不行——必须 n > 0 && ...。
  • 枚举子集边界：sub = (sub-1) & mask 终止于 sub === 0，循环用 sub > 0（空集不进）或包含空集另算。
  • 状态压缩 n 的上限：位掩码 DP 的 mask 是 2^n，n > 22 时 2^n 超千万爆内存——只适合 n ≤ 20。
  • 异或不满足分配律对 & 的某些组合：异或与与混用时注意运算顺序，复杂表达式宁可加括号。

八、进阶方向（链接其他叶） ​

  • 状态压缩 DP：位掩码表示集合 + 子集枚举 —— 见动态规划进阶 叶
  • 树状数组（BIT）：lowbit 函数驱动 —— 见线段树与树状数组 叶
  • 快速幂：位运算思想最优雅的应用（指数按二进制拆位） —— 见快速幂
  • 哈希表：n & (capacity - 1) 求桶下标 —— 见哈希表 叶

权威链接 ​