Python二进制数除法函数实现求助：整数列表输入，禁用内置函数

按照你提供的二进制数低位在前的存储格式（列表第一个元素是最低位），我们可以通过模拟长除法的逻辑来实现除法函数，同时满足返回反转列表（即高位在前）的要求。

实现思路 #

1. 特殊情况处理：除数为0时抛出错误；被除数小于除数时，商为0，余数为被除数。
2. 辅助函数：实现二进制数的大小比较（判断余数是否够减除数），避免直接转换为十进制。
3. 长除法逻辑：
   • 从被除数的最高位（列表末尾元素）开始，逐位将余数左移（乘以2）并加上当前位。
   • 若余数大于等于除数，则减去除数，商对应位设为1；否则商对应位设为0。
4. 格式调整：去除结果的前导零，最后将商和余数列表反转，得到高位在前的结果。

完整代码实现 #

首先添加辅助比较函数，然后实现除法函数：

def is_greater_or_equal(a: list[int], b: list[int]) -> bool:
    """判断低位在前的二进制数a是否大于等于b"""
    def trim_leading_zeros(bin_list: list[int]) -> list[int]:
        trimmed = bin_list.copy()
        while len(trimmed) > 1 and trimmed[-1] == 0:
            trimmed.pop()
        return trimmed
    
    a_trimmed = trim_leading_zeros(a)
    b_trimmed = trim_leading_zeros(b)
    
    if len(a_trimmed) > len(b_trimmed):
        return True
    elif len(a_trimmed) < len(b_trimmed):
        return False
    else:
        # 从高位到低位比较（列表从后往前遍历）
        for i in range(len(a_trimmed)-1, -1, -1):
            if a_trimmed[i] > b_trimmed[i]:
                return True
            elif a_trimmed[i] < b_trimmed[i]:
                return False
        return True  # 两数相等

def binary_division(dividend: list[int], divisor: list[int]) -> tuple[list[int], list[int]]:
    # 处理除数为0的异常
    if all(bit == 0 for bit in divisor):
        raise ValueError("除数不能为0")
    
    # 复制输入列表，避免修改原数据
    dividend_copy = dividend.copy()
    divisor_copy = divisor.copy()
    
    # 去除被除数和除数的前导零（高位的零）
    while len(dividend_copy) > 1 and dividend_copy[-1] == 0:
        dividend_copy.pop()
    while len(divisor_copy) > 1 and divisor_copy[-1] == 0:
        divisor_copy.pop()
    
    # 被除数小于除数，直接返回商0和被除数作为余数
    if not is_greater_or_equal(dividend_copy, divisor_copy):
        return ([0][::-1], dividend_copy[::-1])
    
    remainder = [0]
    quotient = []
    
    # 从被除数的最高位开始处理（列表末尾元素）
    for bit in reversed(dividend_copy):
        # 余数左移一位（乘以2）：低位在前，左移即向列表头部添加0
        remainder.insert(0, 0)
        # 加上当前位
        remainder = binary_addition(remainder, [bit])
        # 去除余数的前导零
        while len(remainder) > 1 and remainder[-1] == 0:
            remainder.pop()
        
        if is_greater_or_equal(remainder, divisor_copy):
            # 余数减去除数
            remainder = binary_subtraction(remainder, divisor_copy)
            quotient.append(1)
        else:
            quotient.append(0)
    
    # 去除商的前导零（此时商是高位在前的格式，前导零在列表头部）
    while len(quotient) > 1 and quotient[0] == 0:
        quotient.pop(0)
    
    # 去除余数的前导零
    while len(remainder) > 1 and remainder[-1] == 0:
        remainder.pop()
    
    # 返回反转后的列表（高位在前）
    return (quotient[::-1], remainder[::-1])

测试示例 #

比如计算二进制数1010（十进制10，低位在前列表为[0,1,0,1]）除以10（十进制2，低位在前列表为[0,1]）：

dividend = [0,1,0,1]
divisor = [0,1]
quotient, remainder = binary_division(dividend, divisor)
print(quotient)   # 输出 [1,0,1]（高位在前的5）
print(remainder) # 输出 [0]

内容的提问来源于stack exchange，提问作者Ge0g