Appearance
位运算基础与常用技巧
计算机的世界是二进制的。不管是数字、文字还是图片，最终都以 0 和 1 的形式存储和处理。
位运算直接操作这些二进制位，绕过了高级抽象，因此速度极快。很多看似复杂的问题，用位运算可以一行代码解决。这也是为什么位运算在算法面试中经常出现——它考察的是对计算机底层的理解。
二进制表示
在深入位运算之前，先确保你理解二进制。
十进制 → 二进制：
十进制 5 的二进制表示：
5 = 4 + 1 = 2² + 2⁰ = 0101（4位表示）
十进制 13 的二进制表示：
13 = 8 + 4 + 1 = 2³ + 2² + 2⁰ = 1101位编号（从右到左，从 0 开始）：
二进制：1 1 0 1
位编号：3 2 1 0
↑ ↑
最高位 最低位在 JavaScript 中查看二进制：
javascript
// 十进制 → 二进制字符串
(13).toString(2); // "1101"
(5).toString(2); // "101"
// 二进制 → 十进制
parseInt("1101", 2); // 13
// 直接使用二进制字面量
const a = 0b1101; // 13
const b = 0b0101; // 5六种位运算符
JavaScript 提供了六种位运算符：
1. 按位与 AND（&）
两位都为 1 才是 1，否则为 0。
1 1 0 1 (13)
& 0 1 0 1 (5)
─────────
0 1 0 1 (5)javascript
13 & 5 // 5应用：检查某位是否为 1、清除某些位、取模运算。
2. 按位或 OR（|）
有一位为 1 就是 1，都是 0 才是 0。
1 1 0 1 (13)
| 0 1 0 1 (5)
─────────
1 1 0 1 (13)javascript
13 | 5 // 13应用：设置某位为 1、合并标志位。
3. 按位异或 XOR（^）
两位不同为 1，相同为 0。
1 1 0 1 (13)
^ 0 1 0 1 (5)
─────────
1 0 0 0 (8)javascript
13 ^ 5 // 8应用：交换两数、找唯一数、加密。
4. 按位取反 NOT（~）
0 变 1，1 变 0。
javascript
~5 // -6
// 原理：JavaScript 使用 32 位有符号整数
// 5 = 00000000 00000000 00000000 00000101
// ~5 = 11111111 11111111 11111111 11111010 = -6（补码表示）规律：~n = -(n + 1)
javascript
~0 // -1
~5 // -6
~(-1) // 05. 左移（<<）
所有位向左移动，右边补 0。
5 << 1:
0 1 0 1 (5)
← 移动 1 位
1 0 1 0 (10)javascript
5 << 1 // 10 (5 × 2)
5 << 2 // 20 (5 × 4)
5 << 3 // 40 (5 × 8)规律：n << k 等于 n × 2^k
6. 右移（>>）
所有位向右移动，左边补符号位（算术右移）。
13 >> 1:
1 1 0 1 (13)
移动 1 位 →
0 1 1 0 (6)javascript
13 >> 1 // 6 (13 / 2 向下取整)
13 >> 2 // 3 (13 / 4 向下取整)
-8 >> 1 // -4 (负数右移，左边补 1)规律：n >> k 等于 Math.floor(n / 2^k)
无符号右移 >>>：左边补 0（不考虑符号位）
javascript
-8 >> 1 // -4 （算术右移）
-8 >>> 1 // 2147483644 （无符号右移）常用位运算技巧
这些技巧在算法题中反复出现，值得记忆。
1. 判断奇偶
javascript
// 奇数的最低位是 1，偶数是 0
n & 1 === 1 // 奇数
n & 1 === 0 // 偶数
// 比 n % 2 更快2. 乘除 2 的幂
javascript
n << 1 // n × 2
n >> 1 // n / 2（向下取整）
n << k // n × 2^k
n >> k // n / 2^k（向下取整）
// 注意：仅适用于正整数3. 交换两数（不用临时变量）
javascript
a = a ^ b;
b = a ^ b; // b = (a^b) ^ b = a
a = a ^ b; // a = (a^b) ^ a = b
// 实际中不建议用，可读性差且可能更慢4. 清除最低位的 1
javascript
n & (n - 1) // 把最右边的 1 变成 0
// 例子：
// n = 1100 (12)
// n-1 = 1011 (11)
// n&(n-1) = 1000 (8) 最右边的 1 被清除应用：统计 1 的个数、判断 2 的幂。
5. 获取最低位的 1
javascript
n & (-n) // 只保留最右边的 1
// 例子：
// n = 0 0 1 1 0 0 (12)
// -n = 1 1 0 1 0 0 (补码)
// n&(-n) = 0 0 0 1 0 0 (4)原理：负数用补码表示，-n = ~n + 1。
6. 判断是否是 2 的幂
javascript
n > 0 && (n & (n - 1)) === 0
// 2 的幂只有一个 1
// 1 = 0001, 2 = 0010, 4 = 0100, 8 = 1000
// n & (n-1) 清除这唯一的 1 后变成 07. 获取/设置/清除某一位
javascript
// 获取第 k 位（k 从 0 开始）
(n >> k) & 1
// 设置第 k 位为 1
n | (1 << k)
// 清除第 k 位（设为 0）
n & ~(1 << k)
// 翻转第 k 位
n ^ (1 << k)示例：
javascript
let n = 13; // 1101
// 获取第 2 位
(n >> 2) & 1 // 1
// 设置第 1 位为 1
n | (1 << 1) // 1111 = 15
// 清除第 2 位
n & ~(1 << 2) // 1001 = 9
// 翻转第 0 位
n ^ (1 << 0) // 1100 = 12异或的神奇性质
异或（XOR）是位运算中最有用的，它有以下性质：
- 自反性：
a ^ a = 0 - 零元素：
a ^ 0 = a - 交换律：
a ^ b = b ^ a - 结合律：
(a ^ b) ^ c = a ^ (b ^ c)
这些性质导出一个重要结论：
一组数连续异或，成对的数会抵消，只留下出现奇数次的数。
javascript
a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b这是「只出现一次的数字」系列问题的核心。
javascript
// 数组 [2, 3, 2]，找只出现一次的数
2 ^ 3 ^ 2 = (2 ^ 2) ^ 3 = 0 ^ 3 = 3位运算的注意事项
1. JavaScript 的 32 位限制
JavaScript 位运算将操作数转换为 32 位有符号整数。
javascript
// 超过 32 位的数会被截断
2 ** 31 | 0 // -2147483648（溢出）
// 浮点数会被截断为整数
5.7 | 0 // 52. 优先级问题
位运算优先级低于比较运算符，容易出错：
javascript
// 错误：先计算 1 === 1，结果是 true，再与 n 做位与
n & 1 === 1 // 实际是 n & (1 === 1)
// 正确
(n & 1) === 13. 负数的位运算
JavaScript 使用补码表示负数。对负数进行位运算要格外小心：
javascript
-1 >> 1 // -1（算术右移，左边补 1）
-1 >>> 1 // 2147483647（无符号右移，变成很大的正数）位运算 vs 常规运算
| 操作 | 位运算 | 常规运算 | 备注 |
|---|---|---|---|
| 判断奇偶 | n & 1 | n % 2 | 位运算更快 |
| 乘 2 | n << 1 | n * 2 | 现代编译器会优化 |
| 除 2 | n >> 1 | Math.floor(n/2) | 正数用位运算更快 |
| 交换 | 异或法 | 临时变量 | 临时变量更清晰 |
在算法题中，位运算的主要优势不是性能，而是提供了独特的解题思路。
本章小结
- 六种运算符：
&（与）、|（或）、^（异或）、~（取反）、<<（左移）、>>（右移） - 常用技巧：判断奇偶、乘除 2、清除/获取最低位的 1、判断 2 的幂
- 异或性质：自反性
a^a=0，零元素a^0=a，交换律，结合律 - 注意事项：32 位限制、优先级、负数补码
下一章我们将学习位运算的应用场景，看看如何用位运算解决实际问题。