tech-interview-handbook 二进制与位运算学习指南：从进制转换到位操技巧的面试实战

tech-interview-handbook 二进制与位运算学习指南：从进制转换到位操技巧的面试实战

【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook

本篇基于 tech-interview-handbook 仓库中的二进制算法学习指南（binary.md），系统讲解编码面试中二进制数制与位运算的核心知识：如何在所选编程语言中完成十进制与二进制的互转、八条必须烂熟于心的位操作技巧、需要重点防范的边界情况，以及配套的精选题目与学习资源。读完本文，你将能够独立写出进制转换逻辑、运用位运算技巧解决面试中的常见位操作题，并清楚该主题在整体面试复习计划中的优先级定位。

二进制主题在面试复习中的定位

在动手深入细节之前，先明确这个话题的分量。二进制学习指南在 学习指南总览 的主题优先级表中被标注为Low（低优先级）：

指南原文给出的判断依据是：对大多数软件工程师而言，日常工作中很少直接处理位（bit），位运算更多出现在底层系统和底层编程语言场景中。因此它对大多数工程师的编码面试来说重要性相对较低——但它仍会被偶尔问到，所以底线要求是：你必须熟练掌握**在你所选编程语言中，把十进制数转成二进制形式（以及反向转换）**的方法。

从站点结构看，该指南通过 sidebars.js 中注册的algorithms/binary条目挂载到算法栏目下，与 array、string、hash-table 等 19 个主题的 cheatsheet 并列（各指南的结构规范可参考仓库中的template.md）。此外，仓库的题库分组数据 QuestionGroups.json 中Add Binary一题也被归类在binary主题下，可见二进制在题库体系中确有独立归类。

实用结论：如果你时间紧张，把 array、string、sorting/searching、tree、graph 等高优先级主题吃透后再回头补二进制；但无论如何，进制转换 + 位运算技巧表这两块是最小必修项。

核心基本功：十进制与二进制的互转

指南反复强调这一点："涉及二进制表示和位运算的题目偶尔会被问到，你必须绝对熟悉如何在你选择的编程语言中把数字从十进制形式转成二进制形式（以及反过来）。"

仓库中的参考实现

仓库在apps/website/experimental/utilities/javascript/目录下提供了两个带自测用例的 JavaScript 参考实现，正好覆盖两个方向：

二进制字符串 → 整数（Hacker 算法），见 binToInt.js：

// Does not handle negative binary numbers. function binToInt(binary) { let res = 0; for (let i = 0; i < binary.length; i++) { res = res * 2 + +binary[i]; } return res; }

核心是res = res * 2 + +binary[i]这一行：从左到右逐位扫描，每一步把已累积的结果左移一位（乘 2），再加上当前位的值。以1100011为例，累积过程为1 → 3 → 6 → 12 → 24 → 49 → 99，与内置解析结果一致。文件末尾用一系列console.log断言把每个用例与parseInt(binary, 2)对拍验证，包括'1100011' === 99这种较长用例。注意源码注释明确说明：不处理负的二进制数——这正是下文 Corner cases 中"负数"要点的实际体现。

整数 → 二进制字符串（短除 2 法），见 intToBin.js：

// Does not handle negative numbers. function intToBin(number) { if (number === 0) { return '0'; } let res = ''; while (number > 0) { res = String(number % 2) + res; number = parseInt(number / 2, 10); } return res; }

思路是反复对 2 取余得到最低位、再整除 2，把余数倒序拼回（所以每轮用String(number % 2) + res前插）。0需要单独处理——这也是仓库实现对指南中"负数/边界"要点的回应：源码注释写明"Does not handle negative numbers"。测试用例覆盖0、1、2、3、5、99，全部与(number).toString(2)对拍一致。

这两个实现值得在面试前手推一遍：如果面试官追问"你内置函数是怎么算的"，你能直接口述出算法本体，而不是只会调 API。

各语言内置转换速查

按template.md 中"Implementations"一节的组织方式，二进制指南实际面试中最常用的是语言内置 API，以下是常用语言的通用写法（面试前先在你的主力语言中验证一遍输出格式）：

注意各语言对负数的行为差异（如 JavaScript 的toString(2)会返回补码表示的长字符串，Python 的bin(-5)得到'-0b101'），这直接关联下一条边界情况。

位运算技巧速查表

指南给出的"Some helpful utility snippets"共 8 条，完整继承如下表：

下面逐条展开原理，帮助理解"为什么这样做对"，而不是机械背诵。

构造掩码：1 << k。所有单比特操作的第一块积木。1 << k得到一个只有第 k 位为 1、其余全 0 的数（bit 编号从 0 开始，即最低位为第 0 位）。后续操作都是拿它与原数做按位组合。

测试第 k 位（AND 测试）。num & (1 << k) != 0：AND 的性质是"两位都为 1 结果才为 1"，掩码其余位全是 0，所以结果要么为 0、要么恰好等于1 << k。这是"数有多少个 1"（Number of 1 Bits 题）的标准逐位扫描法：

function countOneBits(num) { let count = 0; while (num > 0) { count += num & 1; // 只看最低位 num >>= 1; // 右移一位 } return count; }

置 1 位（OR）与清零位（AND NOT）。OR 的性质是"任一为 1 即为 1"，所以num |= (1 << k)只会把第 k 位写成 1，不动其他位；清零则相反，用~(1 << k)构造一个"只有第 k 位是 0、其余全是 1"的掩码再做 AND，只有第 k 位被强制清 0。

翻转位（XOR）。XOR 是"不同为 1"，掩码第 k 位是 1，所以原位是 0 变 1、是 1 变 0，其余位与 0 异或保持不变。这一性质还支撑了两条"交换两变量"的技巧：a^=b; b^=a; a^=b;利用x^x=0与x^0=x完成无临时变量交换。

移位 = 乘除 2 的幂。num << k等价于乘 2 的 k 次方，num >> k等价于整除（向下取整），这也是"除以 2 的 k 次方"条目的来源。面试中凡是看到"×8/÷4"这类操作，应条件反射地想到用移位替代以提升效率——但要记住移位只对整数成立，且对负数的右移在不同语言中语义不同（见下文）。

判断 2 的幂：两条等价的技巧。

• (num & (num - 1)) == 0：2 的幂的二进制形如1000...0，减 1 后变成0111...1，两者 AND 必为 0；非 2 的幂则至少两位为 1，减 1 后不会全被抵消。必须额外要求num > 0，否则0 & (0 - 1) == 0也会误判通过——这是该技巧最容易踩的坑。
• (num & (-num)) == num：利用负数取反的补码性质，-num会"截取"出num最低位的 1（即最低置位位），若这个值等于num本身，说明num只有一个位为 1，即 2 的幂。同样需要num > 0。

这两条也是"Counting Bits"、"Single Number"等题目的底层工具，建议配合下文题目一起练。

Corner cases：边界情况与常见陷阱

指南列出的边界清单只有一句话，但每一条都对应真实会翻车的写法：

• 警惕并检查溢出/下溢（overflow/underflow）：移位操作尤其危险。1 << k在 k 较大时会超出语言整数/浮点表示范围（如 JavaScript 按位运算符只处理 32 位整数，1 << 32的结果与1 << 0相同）；累乘、累加类位运算（如计数、区间求和）也要确认中间值不越界。
• 负数（Negative numbers）：
  • 位运算对负数走补码表示，>>>（逻辑右移）与>>（算术右移）结果不同；
  • 仓库的 intToBin.js 与 binToInt.js 均在注释中声明不处理负数，说明负数处理需要单独设计（如符号位 + 绝对值，或直接依赖语言补码语义）；
  • "判断 2 的幂"技巧需排除num <= 0；
  • 进制转换内置 API 对负数的输出格式因语言而异（前缀0b、负号位置等），面试中先与面试官确认输入范围。

此外，通用面试提示（可参考 学习指南总览 "General interview tips" 一节）同样适用于位运算题：先验证输入、检查 off-by-one、写完代码后用若干样例（如 0、1、2 的幂、负数）自测。

Essential questions：必练题

指南给出的 Essential questions（"如果只练两题，就练这两题"级别）：

1. Sum of Two Integers（两整数之和）—— 用+被禁止后，用&、^模拟加法：carry = a & b，sum = a ^ b，循环把进位左移后相加，直到进位为 0。这道题强制你理解补码加法在位层面的真实过程，是位运算的"压舱石"题。
2. Number of 1 Bits（统计置位比特数）—— 输入一个 32 位无符号整数，统计其二进制中 1 的个数。标准做法即上文"测试第 k 位"的逐位扫描，进阶可学 Brian Kernighan 法num &= (num - 1)逐次消去最低位 1，循环次数恰好等于 1 的个数。

Recommended practice questions：进阶练习题

在吃透上述两题后，指南推荐继续练习：

1. Counting Bits（比特位计数）—— 对0..n逐个统计 1 的个数，考察从f(i)推导f(i)的动态规划式优化（如count[i] = count[i >> 1] + (i & 1)），位运算与 DP 思想的结合点。
2. Missing Number（缺失数字）—— 经典的异或求法：把0..n全部异或再异或一遍数组，成对出现的数被x^x=0抵消，剩下即为缺失值；也考察"不用额外空间"这一约束下的位运算直觉。
3. Reverse Bits（反转比特）—— 直接对 32 位整数逐位右移、把最低位累积到结果的高位（result = (result << 1) | (num & 1); num >>= 1），是"测试最低位 + 移位累积"组合拳的标准模板，也是仓库中 Add Binary 归类 之下 binary 主题的典型题型。
4. Single Number（只出现一次的数字）—— 全数组异或，出现两次的数互相抵消，留下的即答案。它是 XOR 交换性质（a^a=0、a^0=a）的直接应用，务必做到不看题解独立写出。

学习资源与推荐课程

指南为每个主题配三档学习资源，二进制指南（binary.md）的清单为：

• 阅读：basecs 的《Bits, Bytes, Building With Binary》（建立对二进制数制的直观认识）；Wikipedia 的 Bitwise operation 词条（系统参考按位操作全集）。
• 视频：HackerRank 的《Algorithms: Bit Manipulation》（配合题目讲解位操作技巧）。
• 练习：在线交互式位运算练习场（Bit operations 练习页），适合在写代码前热身手感。

指南末尾统一挂载 AlgorithmCourses.md 中的推荐课程（所有算法 cheatsheet 共用同一套课程推荐）：

在仓库中的延伸阅读路径

• 本指南原文：apps/website/contents/algorithms/binary.md
• 算法指南总览与优先级表：apps/website/contents/algorithms/study-cheatsheet.md
• 进制转换参考实现（含自测断言）：binToInt.js、intToBin.js
• 指南结构模板（各 cheatsheet 统一遵循的章节骨架）：template.md
• 题库主题分组数据（binary 主题归类）：QuestionGroups.json

小结：二进制是编码面试中低概率但可完全准备的主题。最小知识集 = 熟练的进制互转（内置 API + 手写算法）+ 八条位操作技巧（重点理解1 << k掩码、2 的幂判定、XOR 抵消）+ 负数与溢出两条边界检查；练习顺序 = Sum of Two Integers、Number of 1 Bits 两题打底，再推进 Counting Bits、Missing Number、Reverse Bits、Single Number 四题巩固。

【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook