• 中文 • Jackey

位运算：掌握底层操作应对高级面试

完整的位运算指南，包含交互式可视化。学习基本位操作、常见模式，并用优化解法解决 LeetCode 问题。

#algorithm #bit-manipulation #bitwise #optimization #visualization #leetcode #interview

为什么位运算在面试中很重要

位运算是使用按位操作在二进制级别解决问题的艺术。虽然它看起来像是底层魔法,但 FAANG 和顶级科技公司的面试官经常测试这些技能,因为它们:

  • 展示深厚的计算机科学理解：你知道计算机实际上是如何工作的
  • 实现时空权衡：许多问题可以用 O(1) 空间解决,而其他方法需要 O(n)
  • 展示优化思维：位操作通常比算术操作快 10-100 倍
  • 测试数学思维：位模式揭示了优雅的数学性质

位运算大放异彩的常见面试场景:

  • 查找唯一元素（XOR 魔法）
  • 子集生成（位掩码枚举）
  • 空间优化（位数组、布隆过滤器）
  • 快速算术（2 的幂的乘除法）

二进制数字基础

在深入操作之前,让我们可视化数字如何用二进制表示:

十进制到二进制（8 位表示）:

5 的二进制:
  位置:      7  6  5  4  3  2  1  0
  位:       0  0  0  0  0  1  0  1
  值:       0  0  0  0  0  4  0  1  = 5

13 的二进制:
  位置:      7  6  5  4  3  2  1  0
  位:       0  0  0  0  1  1  0  1
  值:       0  0  0  0  8  4  0  1  = 13

关键洞察：每个位置代表 2^i

核心位运算操作

1. AND (&): 两个位都必须为 1

  5:  00000101
& 3:  00000011
  ─────────────
  1:  00000001

用例：检查位是否设置、清除位、提取位

2. OR (|): 至少一个位必须为 1

  5:  00000101
| 3:  00000011
  ─────────────
  7:  00000111

用例：设置位、组合标志

3. XOR (^): 位必须不同

  5:  00000101
^ 3:  00000011
  ─────────────
  6:  00000110

用例：切换位、查找唯一元素、无临时变量交换

4. NOT (~): 翻转所有位

~5:  11111010 (8 位二进制补码)

用例：创建掩码、反转标志

5. 左移 (<<): 乘以 2^n

5 << 1:  00000101 -> 00001010 (5 * 2 = 10)
5 << 2:  00000101 -> 00010100 (5 * 4 = 20)

6. 右移 (>>): 除以 2^n

5 >> 1:  00000101 -> 00000010 (5 / 2 = 2)
5 >> 2:  00000101 -> 00000001 (5 / 4 = 1)

交互式可视化：设置和清除位

逐步查看位操作如何工作:

使用 OR 设置位

Step 1 of 4

原始数字：5

Number: 5
07
06
05
04
03
12
01
10

使用 AND 清除位

Step 1 of 4

原始数字：7

Number: 7
07
06
05
04
03
12
11
10

基本位运算模式

模式 1: 单个位操作

Loading...

模式 2: Brian Kernighan 算法（计算设置位）

关键洞察：n & (n-1) 总是移除最低位的设置位！

示例: n = 12 (二进制: 1100)

步骤 1: 12 & 11
  1100  (12)
& 1011  (11)
  ────
  1000  (8)   <- 移除最低位的设置位

步骤 2: 8 & 7
  1000  (8)
& 0111  (7)
  ────
  0000  (0)   <- 移除最低位的设置位

计数: 2 个设置位

模式 3: 2 的幂检查

一个数字是 2 的幂当且仅当它只有一个位被设置。

8:   00001000  -> 8 & 7 = 00001000 & 00000111 = 0 ✓
12:  00001100  -> 12 & 11 = 00001100 & 00001011 = 8 ✗

公式: n > 0 && (n & (n-1)) == 0

模式 4: 获取/隔离最低位的设置位

12:  00001100
-12: 11110100  (二进制补码)
─────────────
&:   00000100  (隔离位置 2 的位)

公式: n & (-n)

LeetCode 问题：从基础到高级

问题一：只出现一次的数字 (LC 136)

问题：给定一个非空数组,其中每个元素出现两次,除了一个元素只出现一次,找到那个只出现一次的元素。

关键洞察：XOR 有神奇的性质:

  • a ^ a = 0（相同的数字抵消）
  • 0 ^ a = a（与 0 的 XOR 是恒等）
  • XOR 是可交换和可结合的

示例：[4, 1, 2, 1, 2]

  4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4
Loading...

复杂度:

  • 时间: O(n)O(n) - 单次遍历
  • 空间: O(1)O(1) - 无额外空间（对比 HashSet 的 O(n)O(n)）

问题二：比特位计数 (LC 338)

问题：对于从 0 到 n 的每个数字,计算其二进制表示中 1 的数量。

关键洞察：使用动态规划和位运算！

模式:
0: 0000 -> 0 位
1: 0001 -> 1 位
2: 0010 -> 1 位  (与 1 相同，右移删除 0)
3: 0011 -> 2 位 (与 1 相同，加 1)
4: 0100 -> 1 位  (与 2 相同，右移删除 0)
5: 0101 -> 2 位 (与 2 相同，加 1)
6: 0110 -> 2 位 (与 3 相同，右移删除 0)
7: 0111 -> 3 位 (与 3 相同，加 1)

公式: result[i] = result[i >> 1] + (i & 1)
Loading...

复杂度:

  • 时间: O(n)O(n) - 单次遍历,每次迭代常量工作
  • 空间: O(1)O(1) - 不包括输出数组

问题三：颠倒二进制位 (LC 190)

问题：颠倒一个 32 位无符号整数的位。

示例:

输入:  00000010100101000001111010011100
输出:  00111001011110000010100101000000

方法：从右到左处理每一位,从左到右构建结果。

Loading...

复杂度:

  • 时间: O(1)O(1) - 总是 32 次迭代
  • 空间: O(1)O(1)

问题四：汉明距离 (LC 461)

问题：找出两个整数之间位不同的位置数量。

关键洞察：XOR 给出位不同的确切位置！

示例：x = 1 (0001), y = 4 (0100)

  0001  (1)
^ 0100  (4)
  ────
  0101  (5)

计算 5 中的设置位: 2 个位置不同
Loading...

复杂度:

  • 时间: O(1)O(1) - 最多 32 位
  • 空间: O(1)O(1)

问题五：使用位掩码生成子集 (LC 78)

问题：生成一个集合的所有可能子集。

关键洞察：每个子集都可以用位掩码表示！

  • 对于 n 个元素,有 2n2^n 个子集
  • 从 0 到 2n−12^n - 1 的每个数字代表一个唯一的子集
  • 如果位 i 被设置,包含元素 i

可视化示例：nums = [1, 2, 3]

掩码   二进制   子集
  0    000      []
  1    001      [1]
  2    010      [2]
  3    011      [1, 2]
  4    100      [3]
  5    101      [1, 3]
  6    110      [2, 3]
  7    111      [1, 2, 3]
Loading...

复杂度:

  • 时间: O(n⋅2n)O(n \cdot 2^n) - 生成 2n2^n 个子集,每个需要 O(n)
  • 空间: O(1)O(1) - 不包括输出

面试技巧和常见陷阱

面试官期望你知道什么

  1. 清楚地解释位运算操作

    • 不要只写代码；解释每个操作为什么有效
    • 如果需要,画出二进制表示

  2. 识别模式

    • XOR 用于查找唯一元素
    • n & (n-1) 用于移除最低位
    • n & (-n) 用于隔离最低位
    • 位掩码用于子集枚举

  3. 讨论权衡

    • “位运算给我们 O(1) 空间对比 HashSet 的 O(n)”
    • “适用于 32/64 位整数但可能溢出”

要避免的常见错误

  1. 忘记运算符优先级

    // 错误: & 的优先级低于 ==
if (n & 1 == 0)  // 解析为: n & (1 == 0)

// 正确: 使用括号
if ((n & 1) == 0)

  2. 有符号与无符号移位（Java/JavaScript）

    -1 >> 1   // -1 (算术移位,符号扩展)
-1 >>> 1  // 2147483647 (逻辑移位,零填充)

  3. 不考虑负数

    • 二进制补码表示可能很棘手
    • 用负数输入测试！

  4. 位位置的 off-by-one 错误

    • 记住：位从右边开始是 0 索引的
    • 位置 0 是最低有效位

要测试的边界情况

  • 零：n = 0
  • 2 的幂：n = 1, 2, 4, 8, ...
  • 所有位都设置：n = -1（或 0xFFFFFFFF）
  • 在不同位置设置单个位
  • 负数（如果适用）

何时不使用位运算

虽然强大,但位运算并不总是答案:

  1. 代码可读性受损：如果你的团队不熟悉位运算,HashSet 解决方案可能更适合可维护性

  2. 问题约束允许更简单的解决方案：如果 n ≤ 1000 且时间不重要,O(n) 空间解决方案也可以

  3. 整数溢出问题：位运算在固定位宽（32 或 64 位）内工作

  4. 问题不自然地映射到位：不要在不适合的地方强制使用位运算

复杂度总结

大多数位运算操作:

  • 时间: O(1)O(1) 对于单个操作,O(k)O(k) 对于 k 位数字（通常 k=32,所以仍然是 O(1)）
  • 空间: O(1)O(1) - 对原始值进行操作

权衡:

  • 优点：极快、空间高效、优雅
  • 缺点：可读性较差、更难调试、固定精度

面试要点

🎯 掌握这些模式:

  1. XOR 用于查找唯一元素（a ^ a = 0）
  2. Brian Kernighan 算法（n & (n-1) 移除最低位）
  3. 2 的幂检查（n > 0 && (n & (n-1)) == 0）
  4. 位掩码用于子集枚举

🎯 要记住的基本操作:

  • 设置位：n | (1 << i)
  • 清除位：n & ~(1 << i)
  • 切换位：n ^ (1 << i)
  • 检查位：(n & (1 << i)) != 0

🎯 总是解释:

  • 为什么位运算适合这个问题
  • 你正在利用的数学性质
  • 时间/空间权衡与替代方法的对比

🎯 练习画图:

  • 在面试中画出二进制表示
  • 帮助可视化和传达你的思考

记住：位运算问题既测试你对计算机基础的理解,也测试你找到优雅、优化解决方案的能力。当你掌握这些模式时,你将用既快速又节省空间的解决方案给面试官留下深刻印象！🚀

← 返回博客列表