分治法二进制乘法Python代码报错求助：非等长二进制计算异常

大家好，我最近用Python 3.5.2写了一个基于分治法的二进制乘法实现，参考了Wikibooks上的算法和UTSC论文第4页的内容，但现在遇到了棘手的问题——代码没法正确处理所有非等长的二进制输入，核心问题出在补零计数异常上，而且不同测试用例的错误表现还不一样，实在搞不定了，来求助各位！

问题详情 #

我的代码在处理等长二进制数时基本正常，但遇到一长一短的情况就会出问题。比如有的测试用例里补零后的长度计算有误，导致分治拆分的位置不对，后续的移位操作也跟着错了，最终输出结果完全不符合预期。

相关内容 #

原代码

def binary_multiply(x, y):
    n = max(len(x), len(y))
    # 补零使两个二进制数长度一致
    x = x.zfill(n)
    y = y.zfill(n)
    
    if n == 1:
        return str(int(x) * int(y))
    
    half = n // 2
    # 拆分二进制数
    a = x[:half]
    b = x[half:]
    c = y[:half]
    d = y[half:]
    
    # 分治计算子问题
    ac = binary_multiply(a, c)
    bd = binary_multiply(b, d)
    ad_bc = binary_multiply(add_binary(a, b), add_binary(c, d))
    ad_bc = subtract_binary(ad_bc, ac)
    ad_bc = subtract_binary(ad_bc, bd)
    
    # 移位操作
    ac = ac + '0' * (2 * half)
    ad_bc = ad_bc + '0' * half
    
    # 合并结果
    result = add_binary(add_binary(ac, ad_bc), bd)
    return result.lstrip('0') or '0'

# 辅助的二进制加法函数
def add_binary(x, y):
    max_len = max(len(x), len(y))
    x = x.zfill(max_len)
    y = y.zfill(max_len)
    carry = 0
    result = []
    for i in range(max_len - 1, -1, -1):
        bit_sum = int(x[i]) + int(y[i]) + carry
        carry = bit_sum // 2
        result.append(str(bit_sum % 2))
    if carry:
        result.append(str(carry))
    return ''.join(reversed(result))

# 辅助的二进制减法函数（假设x >= y）
def subtract_binary(x, y):
    max_len = max(len(x), len(y))
    x = x.zfill(max_len)
    y = y.zfill(max_len)
    borrow = 0
    result = []
    for i in range(max_len - 1, -1, -1):
        x_bit = int(x[i]) - borrow
        y_bit = int(y[i])
        if x_bit < y_bit:
            x_bit += 2
            borrow = 1
        else:
            borrow = 0
        result.append(str(x_bit - y_bit))
    return ''.join(reversed(result)).lstrip('0') or '0'

问题测试用例

• 测试1：输入x="101"（十进制5）、y="11"（十进制3），预期输出"1111"（十进制15），实际输出"1011"（十进制11）
• 测试2：输入x="1100"（十进制12）、y="101"（十进制5），预期输出"111100"（十进制60），实际输出"101100"（十进制44）

测试2的数值追踪

补零阶段：x保持"1100"（长度4），y被补为"0101"（长度4）；half取4//2=2；拆分后a="11"，b="00"，c="01"，d="01"
子问题计算：ac = binary_multiply("11","01") → "0011"；bd = binary_multiply("00","01") → "0000"
ad_bc计算：add_binary(a,b)得到"11"，add_binary(c,d)得到"10"；相乘得到binary_multiply("11","10") → "110"；减去ac得到"110"-"0011"="0011"，再减bd还是"0011"
移位操作：ac变为"0011" + "0000" → "00110000"；ad_bc变为"0011" + "00" → "001100"
合并结果：add_binary("00110000", "001100")得到"00111100"，再加bd"0000"还是"00111100"，但实际我得到的是"101100"，说明中间某个步骤的补零或拆分出了问题...

现在我怀疑是补零后的长度计算或者half的取整逻辑有问题，比如当n是奇数的时候，max(len(x),len(y))得到的n是奇数，half=n//2会导致拆分后前后部分长度不一致，进而影响后续的移位位数？或者补零的时机不对？

希望各位大佬能帮我找找问题所在，谢谢！

内容的提问来源于stack exchange，提问作者Mr.Xyzed