4-1-4、leetcode#67. 二进制求和之位运算详解

📚 前言

在算法刷题中，二进制相关题目常常考察位运算的灵活运用。位运算由于直接操作内存中的二进制位，效率极高，是优化算法性能的重要手段。今天我们就以 LeetCode 67 题「二进制求和」为例，深入拆解其位运算解法的核心逻辑，帮大家搞懂位运算在加法中的应用本质。适合刚接触位运算的同学，也适合想巩固基础的开发者复习~

一、题目回顾

🔍 题目描述： 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。 示例 1： 输入：a = "11", b = "1" → 输出："100" 示例 2： 输入：a = "1010", b = "1011" → 输出："10101"

💡 常规思路： 最直观的想法是将二进制字符串转为十进制整数，求和后再转回二进制字符串。但这种方法在字符串过长时（超过 Python 整数的默认限制？其实 Python 整数无长度限制，但面试中更考察位运算思维），或者在其他语言中会存在溢出问题。因此，位运算解法是更优的选择，也是面试中的高频考点。

二、核心解法：位运算实现二进制加法

先上完整代码，再逐行拆解：

class Solution: def addBinary(self, a: str, b: str) -> str: # 二进制字符串转整数 x, y = int(a, 2), int(b, 2) # 循环处理进位 while y: # 无进位加法结果 answer = x ^ y # 计算进位（左移1位表示进位到下一位） carry = (x & y) << 1 # 更新x为无进位结果，y为进位 x, y = answer, carry # 整数转二进制字符串（去掉前缀'0b'） return bin(x)[2:]

三、关键位运算逻辑拆解

要理解这个解法，核心是搞懂两个位运算的作用：异或（^）和与（&）+ 左移（<<）。我们先回顾基础位运算规则：

• 异或（^）：两个二进制位不同时为 1，相同时为 0 → 等价于「无进位加法」。比如 1^1=0（无进位），1^0=1（无进位），0^0=0。
• 与（&）：两个二进制位都为 1 时才为 1 → 用于判断哪些位需要进位。比如 1&1=1（需要进位），1&0=0（无需进位）。
• 左移（<<1）：将二进制位整体左移 1 位，右边补 0 → 等价于将进位值传递到下一位。比如 1<<1=10（二进制），表示进位 1 到十位。

🔧 核心逻辑： 二进制加法的本质是「无进位加法」+「进位处理」，循环执行这两步，直到没有进位（y=0）为止。

举个例子（a="11", b="1"）：

1. 初始：x = 0b11（3），y = 0b1（1）
2. 第一次循环： answer = 3^1 = 0b10（2）（无进位加法结果） carry = (3&1) <<1 = 0b1 <<1 = 0b10（2）（进位值） 更新 x=2（0b10），y=2（0b10）
3. 第二次循环： answer = 2^2 = 0b0（0）（无进位加法结果） carry = (2&2) <<1 = 0b10 <<1 = 0b100（4）（进位值） 更新 x=0（0b0），y=4（0b100）
4. 第三次循环： answer = 0^4 = 0b100（4）（无进位加法结果） carry = (0&4) <<1 = 0 <<1 = 0（无进位） 更新 x=4（0b100），y=0（循环结束）
5. 返回 bin(4)[2:] → "100"（正确结果）

四、类比十进制中的竖式运算

到这边其实我还是有点迷糊，后面以十进制加法去理解瞬间就通了。我们以98+921为例。把这个运算拆解成无进位和进位的结果去看

第一次循环：98+921=919（无进位）；98+921=100（进位结果，十位和十位相加9+2=10进到百位就是100）。此时x=9119y=100

第二次循环：919+100=019（无进位）；919+100=1000（进位结果，同上百位和百位相加9+1=10进到千位就是1000）。此时x=019,y=1000

第三次循环：019+1000=1019（无进位）；019+1000=0000=0（进位结果，没有要进位的地方所以最后结果是0）

第四次循环：进位结果是0得到答案1019。

ps:整个过程其实就是小学时候教过的竖式运算。只是当我们习惯直接计算答案后反而看不懂一步步拆解的过程：

1. 把参与运算的数按「数位对齐」（个位对个位、十位对十位、百位对百位……）；
2. 按固定方向（加法 / 减法从右到左，乘法从右到左逐位相乘再累加，除法从左到右）逐位计算；
3. 明确处理进位（加法）、借位（减法）、进位累加（乘法）等中间过程；
4. 最终结果按数位对齐输出。

五、位运算拓展技巧

除了加法，位运算还有很多实用场景，整理几个高频技巧：

• 快速乘除 2：x <<1 等价于 x*2，x>>1 等价于 x//2（效率比 * 和 // 高）。上篇文章就是用到这一技巧4-1-3、leetcode#35——二分法中的中位数
• 交换两个数：a, b = b^a, a^b（无需临时变量）。
• 判断奇偶：x&1 ==1 为奇数，x&1 ==0 为偶数。
• 统计二进制中 1 的个数：通过 x & (x-1) 消除最后一个 1，循环计数（比如 x=3（0b11），x&(x-1)=2（0b10），再循环 x=2&1=0，计数 2）。

六、总结

本文通过 LeetCode 67 题，详细拆解了位运算实现二进制加法的核心逻辑，关键在于理解「异或做无进位加法」和「与+左移做进位处理」的组合用法。位运算作为高效的底层操作，在算法优化和面试中都占据重要地位，建议大家多动手练习，熟练掌握基础规则和常用技巧。

如果觉得本文有帮助，欢迎点赞、收藏、关注！后续会持续更新 LeetCode 算法题的深度解析，一起刷题进步～也可以关注我的专栏——《从java开发到大模型，让deepseek带我飞一年》，我将以自学过程中的心得不断更新博客。