汇编中不使用div指令求倒数实现通用快速除法的方法

针对需求——不依赖特定ISA、不用div指令计算任意正数倒数，同时高效实现两个未知数相除（避免循环减法的性能损耗），最通用且高性能的方案是牛顿-拉夫逊迭代法，以下是具体实现细节：

一、牛顿-拉夫逊迭代求倒数 #

核心原理 #

求正数y的倒数1/y时，牛顿迭代的收敛公式为：
x_{n+1} = x_n * (2 - y * x_n)
该公式通过迭代快速逼近真实倒数，仅需2-3次迭代就能达到32位或64位整数运算所需的精度，完全满足性能要求。

32位无符号定点数实现步骤 #

我们采用Q32定点格式（即数值表示为value = real_num * 2^32，对应范围[0, 2^32)，用于存储0 ≤ 1/y < 1的倒数）：

1. 初始近似值估算：
   为快速得到初始迭代值x₀，可利用前导零计数（CLZ）操作：

   • 对y计算前导零个数clz(y)，则y的最高有效位位于第31 - clz(y)位
   • 初始值x₀ ≈ 2^32 / y，用移位操作快速计算：x₀ = 0x80000000 >> (clz(y) - 1)
   • 若目标ISA无硬件CLZ指令，可通过分治法实现快速前导零计数（比如先判断高16位是否为0，再逐步缩小范围），比循环扫描快得多。

2. 迭代收敛计算：
   每次迭代仅需乘法和减法，以32位为例：

   • 计算y * x_n：32位乘32位得到64位结果，取高32位作为Q32格式的乘积（因为y是整数，x_n是Q32，乘积的高32位对应y*x_n的小数部分）
   • 计算2 - y*x_n：用Q32格式的2（即0x100000000）减去上述乘积的高32位
   • 计算新的迭代值x_{n+1} = x_n * (2 - y*x_n)：同样32位乘32位取高32位
   • 重复2次迭代即可达到32位精度，若需要更高精度可增加1次迭代。

通用汇编实现示例（32位无符号） #

; 输入：r0 = y（32位无符号正数）
; 输出：r0 = 1/y的Q32表示（即(1/y)*2^32）

; 步骤1：计算初始近似值x0
mov r1, #0x80000000  ; 2^31
clz r2, r0           ; 计算前导零个数（无硬件CLZ则用分治法实现）
sub r2, r2, #1
lsr r0, r1, r2       ; x0 ≈ 2^32 / y

; 第一次迭代
mul r3, r0, r1       ; r3 = y * x0（取高32位）
mov r4, #0x100000000 ; Q32格式的2
sub r4, r4, r3       ; 2 - y*x0
mul r0, r0, r4       ; 更新x为x0*(2 - y*x0)，取高32位

; 第二次迭代（提升精度至32位）
mul r3, r0, r1
sub r4, #0x100000000, r3
mul r0, r0, r4

; 此时r0即为1/y的Q32定点数

二、基于倒数实现两个未知数相除（x/y） #

得到1/y的Q32表示后，除法逻辑和你之前处理常数除法的思路一致：

1. 将被除数x转为Q32格式：x << 32（32位无符号数可放入64位寄存器的高32位）
2. 执行64位乘法：(x << 32) * inv_y_Q32
3. 取乘积的高32位，即为x/y的整数部分（若需要小数部分可保留低32位）

除法汇编示例 #

; 输入：r0 = x，r1 = y
; 输出：r0 = x//y（整数除法，向下取整）

bl compute_inv_y     ; 调用倒数计算函数，r1返回1/y的Q32表示
mov r2, r0, lsl #32  ; x转为Q32格式
mul r2, r2, r1       ; 64位乘法，高32位为x/y的整数部分
mov r0, r2, lsr #32  ; 提取结果

三、其他可选方案 #

• Goldschmidt算法：与牛顿迭代类似，通过迭代逼近倒数，适合流水线架构，但实现复杂度略高
• 查表+插值：仅适合小范围的y，通用性不足，不推荐用于任意正数

性能说明 #

牛顿迭代法仅需2-3次乘法和减法操作，时间复杂度为O(1)，性能远优于循环减法（O(n)），且仅依赖基础的移位、乘法、减法指令，完全不依赖特定ISA的div指令，可移植性极强。

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