Python 实现二进制加法

在计算机科学中，二进制加法是一种基本的算术运算。给定两个二进制数，我们需要将它们相加，并返回它们的和。这个问题可以通过模拟手动加法的方式来解决，即从最低位（右侧）开始逐位相加，处理进位，然后向左移动一位，直到所有的位都被处理完毕。

以下是一个 Python 函数，它接受两个字符串作为参数，这两个字符串分别代表两个二进制数。函数返回它们的和，也是一个字符串形式的二进制数。

def add_binary(a, b):
    # 初始化一个列表来保存结果，初始值为 0（进位）
    result = [0]
    # 从字符串的末尾开始遍历（即最低位开始）
    i = len(a) - 1
    j = len(b) - 1
    carry = 0
    # 当两个字符串都还有位时，进行逐位相加
    while i >= 0 or j >= 0 or carry:
        # 如果 a 还有位，则加上 a 的当前位，否则加上 0
        x = int(a[i]) if i >= 0 else 0
        # 如果 b 还有位，则加上 b 的当前位，否则加上 0
        y = int(b[j]) if j >= 0 else 0
        # 计算当前位的和以及进位
        sum = x + y + carry
        carry = sum // 2  # 整除得到进位
        result.append(sum % 2)  # 求余得到当前位的值
        # 移动到下一个位
        i -= 1
        j -= 1
    # 将结果反转，因为我们是从低位到高位计算的
    return ''.join(map(str, result[::-1]))

这个函数使用了一个列表来保存中间结果。列表的初始值为一个进位值 0。然后，我们从字符串的末尾开始遍历，即最低位开始。在每一步中，我们取出两个字符串的当前位（如果字符串还有位的话），加上进位值，然后计算当前位的和以及进位。我们将当前位的值添加到结果列表中，并更新进位值。最后，我们返回结果列表的反转字符串形式，因为我们是从低位到高位计算的。

这个函数的时间复杂度是 O(max(m, n))，其中 m 和 n 分别是两个输入字符串的长度。这是因为我们需要遍历两个字符串的所有位，以及处理可能存在的进位。

以下是一个使用示例：

a = '1010'
b = '1011'
print(add_binary(a, b))  # 输出: '10101'

在这个示例中，我们将二进制数 ‘1010’ 和 ‘1011’ 相加，得到结果 ‘10101’。