illegalCreed

中文

English

中文

English

Appearance

常用位运算技巧 ​

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

速查 ​

  • 判断奇偶：n & 1——结果为 1 是奇数、0 是偶数（比 n % 2 更直接，看最低位即可）。
  • 不用临时变量交换两数：a ^= b; b ^= a; a ^= b;——利用异或自反性 a^a=0，三个异或完成交换，无需第三个变量。
  • 去掉最低位的 1：n & (n - 1)——n-1 让最低位的 1 变 0、其后的 0 全变 1，相与后恰好抹掉那一位。是统计 1 的个数（汉明重量）、判断 2 的幂的核心。
  • 取出最低位的 1（lowbit）：n & (-n)——补码 -n = ~n + 1 的特性使相与后只剩最低位的 1。树状数组（BIT）的 lowbit 函数就是它，也用于分离最低位 1。
  • 判断 2 的幂：n > 0 && (n & (n - 1)) === 0——2 的幂只有一个 1，n&(n-1) 抹掉它后必为 0。注意先判 n > 0（0 和负数不是 2 的幂）。
  • 取第 k 位：(n >> k) & 1——右移把第 k 位移到最低位，再与 1 取出。
  • 置第 k 位为 1：n | (1 << k)——或上一个第 k 位为 1 的掩码。
  • 清第 k 位为 0：n & ~(1 << k)——与上一个第 k 位为 0、其余为 1 的掩码。
  • 翻转第 k 位：n ^ (1 << k)——异或上一个第 k 位为 1 的掩码（异或 1 翻转）。
  • 位运算优先级低于比较：&|^<<>> 优先级都低于 ==/</>，n & 1 == 0 实际是 n & (1==0)——永远加括号 (n & 1) === 0。
  • 复杂度：以上技巧全部 O(1)；统计 1 的个数是 O(位数) = O(log n)。

一、判断奇偶：看最低位 ​

二进制下，偶数最低位是 0、奇数最低位是 1（因为 2^0 = 1 是唯一奇数权位）。所以：

js
function isOdd(n) { return (n & 1) === 1; }   // 最低位为 1 即奇数
function isEven(n) { return (n & 1) === 0; }   // 最低位为 0 即偶数
  • 比 n % 2 更直接：% 要做除法（虽然编译器常优化），& 1 只看一位。
  • 负数也对：补码下 -3 & 1 === 1（-3 是全 1 ...1101，最低位 1），所以 (-3 & 1) === 1 判奇偶成立。
  • 坑：必须加括号——(n & 1) === 0，不能写 n & 1 === 0（后者是 n & (1===0) = n & false = n & 0 = 0，永远 falsy）。

二、不用临时变量交换两数 ​

利用异或自反性，三个异或完成交换，无需第三个变量：

js
function swap(a, b) {
  a ^= b;   // a = a ^ b
  b ^= a;   // b = b ^ (a ^ b) = a
  a ^= b;   // a = (a ^ b) ^ a = b
  return [a, b];
}
  • 推导：第二步代入「此时的 a = a^b」，b_new = b ^ (a^b) = a（b 与自身抵消）；第三步 a_new = (a^b) ^ a_new_b = (a^b) ^ a = b。
  • 适用场景：寄存器紧张的嵌入式环境、炫技题、某些面试题（如「不用额外空间交换」）。日常代码不推荐——可读性差，且现代编译器对临时变量交换优化得更好（寄存器分配甚至不占内存）。
  • 致命陷阱：若 a、b 指向同一内存位置（如数组 a[i] 与 a[i] 交换），第一步 a[i] ^= a[i] 后变 0，后面全错——所以要先判 i !== j。

三、n & (n-1)：去掉最低位的 1 ​

这是位运算最经典的技巧。n-1 的二进制效果是：从最低位的 1 开始（含），以下所有位全翻转（借位传导）。

n     = 101100    最低位的 1 在 bit2
n - 1 = 101011    bit2 及以下全翻转
n & (n-1) = 101000  恰好抹掉最低位的 1

核心用途：统计二进制中 1 的个数（汉明重量）——每次 n &= n - 1 抹掉一个 1，循环几次就有几个 1：

js
function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;   // 抹掉最低位的 1
    count++;
  }
  return count;
}
  • 比「逐位 n & 1 再右移」快——后者固定循环 32 次，前者只循环「1 的个数」次（稀疏的 1 越少越快）。
  • 判断 2 的幂：2 的幂只有一个 1，n & (n-1) 抹掉后为 0。

四、lowbit：取出最低位的 1 ​

n & (-n) 取出 n 中最低位的 1（其余位清零）。原理来自补码：-n = ~n + 1，取反让最低位 1 及以下的 0 全翻转，再 +1 进位回来，恰好在最低位 1 处保留 1。

n     = 101100      最低位的 1 在 bit2
-n    = 010100      （补码：~n+1）
n & (-n) = 001000   只剩最低位的 1
js
function lowbit(n) { return n & (-n); }
lowbit(12)   // 12 = 0b1100，lowbit = 0b0100 = 4
lowbit(10)   // 10 = 0b1010，lowbit = 0b0010 = 2
  • 树状数组（Fenwick Tree / BIT）的基石：BIT 的 lowbit(i) 决定节点管辖的区间长度，整个数据结构建立在这个函数上——见线段树与树状数组 叶。
  • 分离最低位 1：当你要单独处理最低位的 1（如某些位 DP、格雷码相关），lowbit 一步到位。

五、判断 2 的幂 ​

2 的幂（1, 2, 4, 8, ...）的二进制只有一个 1，所以 n & (n-1) === 0：

js
function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}
  • 必须先判 n > 0：n = 0 时 0 & -1 === 0 会误判，n < 0（如 -8 = ...11111000）也只有一个 1 但不是 2 的幂。
  • 替代法：n > 0 && (n & (-n)) === n（2 的幂的 lowbit 等于自身）——等价但不如 n&(n-1) 直观。

六、取、设、清、翻某位 ​

操作第 k 位（最低位为第 0 位）的四个模板，掩码 1 << k 是核心：

js
// 取第 k 位（0 或 1）
const getBit = (n, k) => (n >> k) & 1;

// 置第 k 位为 1
const setBit = (n, k) => n | (1 << k);

// 清第 k 位为 0
const clearBit = (n, k) => n & ~(1 << k);

// 翻转第 k 位
const toggleBit = (n, k) => n ^ (1 << k);
  • 取位：右移把目标位移到最低位，再 & 1 隔离。
  • 置位：用或——| 1 得 1、| 0 保留。
  • 清位：用与——掩码是 ~(1<<k)（第 k 位为 0、其余为 1），与上它清零第 k 位、保留其余。
  • 翻位：用异或——^ 1 翻转、^ 0 保留。

这一组模板是**权限标志位、状态压缩、位图（bitmap）**的基石——任何「用整数当布尔数组」的场景都靠它们。

下一步 ​

掌握了单点技巧后，下一步是把它们组合成完整算法——只出现一次的数字（异或）、不用加减法求和（异或+进位）、汉明重量、状态压缩 DP、权限标志位，见经典应用与位掩码。