简介

本文系统性地探讨了六种典型除法器实现方案，涵盖硬件级位操作算法与数值优化方法，重点解决定点数处理中的精度控制与舍入误差问题。主要内容包括：

1. 硬件级算法实现

2. 高性能优化方案

3. 位扩展技巧：

文档提供可直接运行的Python参考实现，位操作可视化说明和算法复杂度分析，适合嵌入式系统开发者、硬件算法工程师及对数值计算感兴趣的研究人员参考。

注：输入为S0I8F0定点数格式（无符号8位整数）
输出为S0I8F8定点数格式（无符号8位整数，8位小数）

基础处理

四舍五入函数

python">def round_half_up(x):return int(math.floor(x + 0.5))

• 设计目的：解决Python原生round()函数的"bankers rounding"问题（0.5舍入到最近的偶数）

• 实现原理：

  • x + 0.5：将小数点后第一位>=5的值向上提升

  • math.floor()：向下取整实现传统四舍五入

• 示例：

  • round_half_up(1.5) → 2
    • round_half_up(2.5) → 3

舍入判断函数

def need_round_up(remainder, divisor):return remainder * 2 >= divisor

• 数学原理：
  • 当余数 ≥ divisor/2 时满足四舍五入条件
  • 等价于比较：remainder ≥ divisor//2 (整数除法)
• 避免浮点运算：用乘法代替除法比较

全精度基础除法

python">def full_precision_divide(dividend, divisor):if divisor == 0:return Nonequotient = (dividend / divisor) * (1 << 8)return round_half_up(quotient)

• 数据格式转换：
  • dividend / divisor：得到标准浮点商
  • * (1 << 8)：转换为S0I8F8格式（乘以256）
• 错误处理：显式检查除零错误

恢复余数除法

python">def restoring_remainder_division(dividend, divisor):a = dividend << 8  # 扩展小数位q = 0remainder = 0for i in range(16):  # 处理16位小数bit_pos = 15 - i  # 从高位到低位#余数左移1位，腾出低位;将被除数当前位（bit_pos）的值加入余数的最低位remainder = (remainder << 1) | ((a >> bit_pos) & 1) if remainder >= divisor:q |= 1 << bit_pos  # 设置商位remainder -= divisor  # 恢复余数if need_round_up(remainder, divisor):q += 1  # 四舍五入return q

• 硬件算法模拟：
  1. 位扩展：dividend << 8 将整数转换为Q8格式定点数
  2. 循环处理：16次迭代对应8位整数+8位小数
  3. 位提取：(a >> bit_pos) & 1 按位获取被除数
  4. 余数恢复：当余数不够减时恢复原值

不恢复余数除法

def non_restoring_division(dividend, divisor):remainder = 0sign = 1  # 余数符号for i in range(16):remainder = (remainder << 1) | ((a >> (15 - i)) & 1)if sign == 1:if remainder >= divisor: #余数大于被除数q |= 1 << (15 - i)   #设置商位remainder -= divisor #更新余数sign = 1             # 余数为正else:sign = 1  # 保持正号else:if remainder + divisor <= 0:  # 负余数处理q |= 1 << (15 - i)remainder += divisorsign = -1if remainder < 0:remainder += divisor  # 最终余数修正if need_round_up(remainder, divisor):q += 1return q

• 关键差异：
  • 允许余数为负
  • 根据余数符号选择加/减操作
  • 最终需要修正余数符号

LUT

python">_lut = {d: 1.0 / d for d in range(1, 256)}def lut_division(dividend, divisor):if divisor not in _lut:return Nonequotient = dividend * _lut[divisor]return round_half_up(quotient * (1 << 8))

• 预计算优化：
  • LUT存储除数倒数
  • 避免实时计算倒数
• 限制条件：
  • 仅支持1-255的除数
  • 依赖浮点运算精度

二分法

def binary_bit_division(dividend, divisor):a = dividend << 9  # 扩展9位空间q = 0remainder = 0for i in range(17):  # 17位精度bit = (a >> (16 - i)) & 0x1   #依次从高到底提取对应位remainder = (remainder << 1) | bit #将提取的位数加到余数上if remainder >= divisor:q |= 1 << (16 - i)  #设置商位remainder -= divisorq = (q >> 1) + (q & 0x1)  # 右移1位后，若最低位为1则加1，舍入处理return q

• 精度扩展设计：
  • <<9 提供1位保护位(guard bit)
  • 17次循环计算17位中间结果
• 舍入技巧：
  • q >> 1：舍弃保护位
  • + (q & 0x1)：根据保护位决定是否进位

牛顿-拉夫逊迭代法

python">def newton_raphson_division(dividend, divisor, iterations=4):x = 1.0 / max(divisor, 1e-9)  # 防止除零for _ in range(iterations):x *= 2 - divisor * x  # 迭代公式quotient = dividend * xreturn round_half_up(quotient * (1 << 8))

• 数值分析：
  • 初始值：x₀ = 1/divisor
  • 迭代公式：xₙ₊₁ = xₙ(2 - D·xₙ)
  • 平方收敛：每次迭代精确位数翻倍
• 安全措施：
  • max(divisor, 1e-9) 避免除零
  • 4次迭代可达单精度浮点精度