How do you add two binary numbers without using built-in functions?

To add binary numbers manually, simulate the binary addition process starting from the rightmost bit, managing the carry as you go.

Can bitwise operations speed up the Add Binary solution?

Yes, bitwise operations like XOR and AND can be used to handle binary addition and carry calculations more efficiently, especially for large strings.

How should you handle carry in binary addition?

During binary addition, if the sum exceeds 1, a carry of 1 is passed to the next higher bit. Ensure this is managed for each pair of bits.

What are the time and space complexities for the Add Binary problem?

The time complexity is O(max(m, n)) where m and n are the lengths of the input strings. Space complexity is also O(max(m, n)) for storing the result.

What if the binary strings have different lengths?

If the binary strings have different lengths, align them by padding the shorter one with leading zeros, then proceed with the addition as usual.

#67

Easy

auto_awesome数学·string

LeetCode 题解工作台

二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。示例 1：输入: a = "11", b = "1" 输出： "100" 示例 2：输入： a = "1010", b = "1011" 输出： "10101" 提示： 1 4 a 和 b 仅由字符 '0' 或 '1' 组成…

数学字符串位运算模拟

题目描述

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"
输出："100"

示例 2：

输入：a = "1010", b = "1011"
输出："10101"

提示：

1 <= a.length, b.length <= 10⁴
a 和 b 仅由字符 '0' 或 '1' 组成
字符串如果不是 "0" ，就不含前导零

lightbulb

解题思路

方法一：模拟

我们用一个变量 $\textit{carry}$ 记录当前的进位，用两个指针 $i$ 和 $j$ 分别指向 $a$ 和 $b$ 的末尾，从末尾到开头逐位相加即可。

时间复杂度 $O(\max(m, n))$ ，其中 $m$ 和 $n$ 分别为字符串 $a$ 和 $b$ 的长度。空间复杂度 $O(\max(m, n))$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        ans = []
        i, j, carry = len(a) - 1, len(b) - 1, 0
        while i >= 0 or j >= 0 or carry:
            carry += (0 if i < 0 else int(a[i])) + (0 if j < 0 else int(b[j]))
            carry, v = divmod(carry, 2)
            ans.append(str(v))
            i, j = i - 1, j - 1
        return "".join(ans[::-1])

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you handle carry properly when adding binary digits?
question_mark
Can you optimize the solution for large input sizes?
question_mark
Will you account for cases where the binary strings have different lengths?

warning

常见陷阱

外企场景

error
Ignoring the carry during addition can lead to incorrect results.
error
Not managing string length differences properly may cause out-of-bounds errors.
error
Forgetting to remove leading zeros from the final result can lead to invalid outputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Add Two Binary Strings with Overflow Handling
arrow_right_alt
Multiply Binary Numbers
arrow_right_alt
Convert Binary Sum to Decimal and Then Binary

help

常见问题

外企场景

继续练习

#13 罗马数字转整数 #12 整数转罗马数字 #166 分数到小数