✨ 位运算的本质 👌

• 核心概念
• 快速上手
• JS 中的位运算符
• 常用技巧与解释
• JS 特性与注意事项
• 进行验证
• 小结与后续

要点速览

• 位运算是以二进制“位”为粒度的常数时间操作，适合性能敏感场景。
• 常见用途：掩码（多状态压缩）、快速取模、奇偶判断、低位提取、环形索引。
• JavaScript 位运算会把 Number 转为 32 位有符号整数再运算（注意溢出与符号扩展）。
• 等价关系如 x % (2^k) === x & ((2^k) - 1) 需在正确前提下使用（m 为 2 的幂、域内非负）。

复习位运算的概念：

• 以二进制为单位进行运算，直接作用于“位”。
• 常用于性能敏感场景、状态压缩、快速判断与映射。
• 与逻辑运算不同，位运算会对数值进行 32 位整型规约（JavaScript）。

位运算使用层面的本质：在常数时间内对特定位进行读写、清除、切换或提取。

核心优势：快速、可组合（掩码）、适合底层数据结构（环形缓冲、布隆过滤器、位图等）。

---

核心概念

原码 / 反码 / 补码（详解）

• 正数：原码 = 反码 = 补码（最高位符号为 0）。
• 负数：补码 = 原码（除符号位外）按位取反，再加 1。
• 口诀：
  • 负数转补码：按位取反再加一。
  • 从补码还原负数：按位取反再加一，最后加负号。

为什么计算机选择补码？

• 统一加法器：加法和减法都可用同一加法电路完成（a - b === a + (-b)）。
• 零唯一：补码表示下只有一个 0（0000 0000），避免原码/反码的“正零/负零”。
• 自然溢出：超出范围的结果会自动按 2^n 回绕（模环），与底层硬件高效匹配。

8 位有符号整数（n = 8）示例与范围

范围：-128 ~ 127
+5 的原码/反码/补码：0000 0101
-5 的补码：取 +5 的位按位取反 -> 1111 1010；再 +1 -> 1111 1011
-1 的补码：1111 1111（所有位为 1）
-128 的补码：1000 0000（最小值的特殊表示）

从十进制到补码（负数）与从补码还原十进制

十进制负数 -> 补码：
1) 写出该数的绝对值的二进制
2) 除符号位外按位取反
3) +1 得到补码（符号位为 1）

补码 -> 十进制负数：
1) 除符号位外按位取反
2) +1 得到绝对值的二进制
3) 取负号

与常见位运算的关系（两条很实用的等式）

• -x === (~x + 1)（取反加一得到相反数）
• ~x === -x - 1（按位取反等价于“负值减一”）
• 推论：n & -n 可快速取得最低位的 1

在 JavaScript 中的注意点

• JS 在位运算前会把 Number 规约为 32 位有符号整数（补码表示）。
• 算术右移 >> 会用符号位填充高位；逻辑右移 >>> 高位补 0（结果非负）。
• 取反 ~x 受 32 位规约影响，结果可能与期望的 Number 不同。

快速上手

下面用最小例子直观理解常见位运算与掩码用法：

// 低位提取与取模（2 的幂）
const idx = 51 & (16 - 1); // 51 % 16 -> 3

// 奇偶判断
const isEven = (n) => (n & 1) === 0;

// 置位 / 清位 / 翻转第 k 位
const setBit = (n, k) => n | (1 << k);
const clearBit = (n, k) => n & ~(1 << k);
const toggleBit = (n, k) => n ^ (1 << k);
const hasBit = (n, k) => ((n >> k) & 1) === 1;

// 获取最低位的 1
const lowBit = (n) => n & -n;

---

JS 中的位运算符

• & 按位与：两位都为 1 时结果为 1。
• | 按位或：有一位为 1 时结果为 1。
• ^ 按位异或：两位不同为 1，相同为 0。
• ~ 按位取反：每一位翻转（注意 JS 32 位规约后返回有符号整数）。
• << 左移：低位补 0；可能导致溢出。
• >> 算术右移：用符号位填充高位（保留正负号）。
• >>> 逻辑右移：高位补 0（不保留符号），结果非负。

示例：

// 与、或、异或
0b1010 & 0b1100; // 0b1000 -> 8
0b1010 | 0b1100; // 0b1110 -> 14
0b1010 ^ 0b1100; // 0b0110 -> 6

// 取反（32 位规约）
~0; // -1
~1; // -2

// 左移 / 右移
1 << 3; // 8
-8 >> 1; // -4（算术右移，保留符号）
8 >>> 1; // 4（逻辑右移，高位补 0）

// 快速向零取整（32 位规约）
~~3.9; // 3
~~-3.9; // -3

---

常用技巧与解释

1. 模数 m 是 2 的幂时，x % m === x & (m - 1)

• 数学直觉：m = 2^k 时，x % m 等价于保留 x 的低 k 位。
• 位解释：m - 1 的二进制是 k 个 1；x & (m - 1) 会清零高位，保留低位。

m = 8 (2^3)  => m-1 = 7  = 0000 0111
m = 16 (2^4) => m-1 = 15 = 0000 1111
m = 32 (2^5) => m-1 = 31 = 0001 1111

const m = 16; // 2 的幂
const x = 51; // 0b0011_0011
x % m === (x & (m - 1)); // true -> 51 % 16 === 51 & 15 === 3

2. n & (n - 1)：清除 n 的最低位 1

let n = 0b101100; // 44
n & (n - 1); // 0b101000 -> 40

// 计算二进制中 1 的个数（Kernighan 算法）
function bitCount(x) {
  let c = 0;
  while (x) {
    x &= x - 1;
    c++;
  }
  return c;
}

原理解释（为什么能“清除最低位的 1”）

• 从最低位的 1 开始，n - 1 会将该位及其右侧的所有位翻转（最低位的 1 变为 0，其右侧的 0 变为 1）。
• 与运算 n & (n - 1) 会把这两处不同位置上互为 1/0 的位清为 0，从而恰好把最低位的 1 清除，其左侧高位保持不变。

示例（以 n = 0b101100 为例）：

n      = 101100
n - 1  = 101011
n & n-1= 101000  ← 最低位的 1 被清除

与 bitCount 的关系与复杂度

• 每次执行 x &= x - 1 都会清除一个最低位的 1。
• 因此循环次数恰为二进制中 1 的个数（也称 popcount），时间复杂度为 O(k)（k 为 1 的个数），通常优于逐位扫描 O(word_size)。

边界与注意事项（JavaScript）

• n = 0：0 & -1 === 0，不会进入循环，计数结果为 0。
• 负数：JS 位运算以 32 位补码进行，表达的是该补码的位图；n & (n-1) 在位级上仍成立，但结果也是 32 位有符号整数，注意语义（例如用于计数时不传入负数）。
• 大数：位运算会把 Number 规约为 32 位整数，若值超出 32 位范围会丢失高位信息；对位操作场景而言这是预期，但请避免用于超大整数统计。

常见用途

• 快速判断 2 的幂：(n > 0) && ((n & (n - 1)) === 0)。
• 逐个清除最低位的 1：做 popcount、集合大小统计、位图迭代等。
• 与 n & -n 配合：先用 low = n & -n 取最低位的 1（其权值），再用 n &= n - 1 清除它，实现“读取后清除”的迭代策略。

3. 是否为 2 的幂

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

4. 取最低位的 1：n & -n

• 原理：-n 等价于 ~n + 1（补码）。

const n = 0b101100; // 44
const lowBit = n & -n; // 0b000100 -> 4

5. 奇偶性判断

const isEven = (n) => (n & 1) === 0;
const isOdd = (n) => (n & 1) === 1;

6. 置位 / 清位 / 翻转第 k 位

// 置位（设为 1）
function setBit(n, k) {
  return n | (1 << k);
}
// 清位（设为 0）
function clearBit(n, k) {
  return n & ~(1 << k);
}
// 翻转位（0->1, 1->0）
function toggleBit(n, k) {
  return n ^ (1 << k);
}
// 读位（是否为 1）
function hasBit(n, k) {
  return ((n >> k) & 1) === 1;
}

7. 异或交换（不使用临时变量）

let a = 5,
  b = 9;
a ^= b;
b ^= a;
a ^= b; // 交换

注意：不要对同一变量执行该模式（例如 a ^= a 会清零）。

8. 位掩码（多状态压缩）

// 权限位
const READ = 1 << 0; // 0001
const WRITE = 1 << 1; // 0010
const EXEC = 1 << 2; // 0100

let perm = READ | WRITE; // 0011
perm = setBit(perm, 2); // 开启 EXEC -> 0111
hasBit(perm, 1); // 是否有 WRITE -> true
perm = clearBit(perm, 0); // 关闭 READ -> 0110

9. 环形数组 / 快速映射到区间 [0, 2^k)

const capacity = 1024; // 2 的幂
const mask = capacity - 1; // 1023
let i = 0;
function nextIndex() {
  i++;
  return i & mask;
} // 比 x % capacity 更快

---

JS 特性与注意事项

• 32 位规约：位运算会将 Number（64 位浮点）先转换为有符号 32 位整数再运算，结果再转回 Number。
• >>>（无符号右移）总是返回非负数；>>（算术右移）保留符号。
• 溢出与符号位：1 << 31 得到 -2147483648；(1 << 31) >>> 31 === 1。
• x % m === x & (m - 1) 只在 m 为 2 的幂且 x 非负（或明确在 32 位整型域内）时等价。
• BigInt 也支持位运算（& | ^ ~ << >>），但不能与 Number 混用。
• 可读性优先：位技巧应配上注释或封装为函数，避免魔法数字。

常见误区

• 在 m 不是 2 的幂或 x 为负数时，误用 x & (m - 1) 替代 %。
• 混用 Number 与 BigInt 做位运算（将抛错）；忽视 32 位规约导致溢出。
• 误解 >> 与 >>> 的差异：负数逻辑右移（>>>）会变为很大的正数。
• 过度使用异或交换，导致可读性差且出现边界问题（如同一变量参与）。

使用建议

• 封装常用位操作为小工具函数（setBit、clearBit 等），并为掩码常量命名。
• 对外暴露人类可读的 API，内部再用位运算做压缩与优化。
• 在哈希映射、环形缓冲、权限系统等场景优先考虑 2 的幂容量，以便快速取模。

---

进行验证

// 验证：x % m === x & (m - 1)
for (let m of [2, 4, 8, 16, 32, 64]) {
  for (let x = 0; x < 200; x++) {
    if (x % m !== (x & (m - 1))) {
      throw new Error(`不等价: x=${x}, m=${m}`);
    }
  }
}

// 验证：n & (n-1) 清除最低位 1
console.assert((0b101100 & (0b101100 - 1)) === 0b101000);

// 验证：最低位的 1
console.assert((0b101100 & -0b101100) === 0b000100);

以上示例可在浏览器 Console 或 Node.js 中直接运行。

---

小结与后续

1. 位运算以“位”为粒度进行常数时间操作，适合状态压缩与快速映射。
2. 在 JS 中需注意 32 位规约与符号扩展，避免溢出与误用运算符差异。
3. 掩码设计与 2 的幂容量能显著简化取模与索引；请配合清晰命名与封装。
4. 后续可结合位图、布隆过滤器、环形缓冲等数据结构进一步应用位运算。