1. 从“除不尽”到“算得准”为什么我们需要定点除法在嵌入式开发、数字信号处理或者自己动手写一个精简的CPU模拟器时你大概率会遇到一个绕不开的问题硬件没有浮点运算单元FPU。这时候所有带小数点的计算都得靠整数来“模拟”。加法、减法、乘法还好说但一到除法头疼的事情就来了。浮点数除法直接用一个“/”操作符编译器或硬件就帮你搞定了但在定点数Fixed-Point的世界里这个“/”背后是一整套精巧有时也略显繁琐的算法在支撑。我最初接触定点除法是在为一个低成本的微控制器编写电机控制算法。电机的转速、位置环计算需要高动态的除法运算而芯片的算力只够做整数运算。直接把浮点算法搬过来编译出来的代码又慢又占地方根本跑不动实时控制。这时候就必须深入到底层去理解计算机是如何用最基本的加法、减法和移位操作一步步“拼”出除法结果的。这个过程就像用乐高积木搭建一座复杂的建筑虽然每一块都很简单但组合起来的逻辑却非常考验设计。定点除法的核心目标就是把一个除法问题转化为一系列可被硬件高效执行的加、减和移位操作。它不直接处理小数点而是通过约定一个隐含的“缩放因子”把所有参与运算的数都视为整数。最终结果也是一个整数但你需要知道这个结果对应的小数点位置在哪里。听起来有点抽象别急我们一步步拆开看。今天要聊的就是其中最经典、也最体现计算机思维的两类算法原码除法和补码除法以及它们的具体实现策略——恢复余数法和加减交替法不恢复余数法。理解了这些你不仅能写出高效的定点数运算库更能深刻体会到计算机算术设计的精妙之处。2. 原码除法符号与数值分开处理的朴素哲学当我们说“原码除法”时指的是操作数的符号和数值部分分开处理。这非常符合人类的直觉先确定结果是正还是负同号为正异号为负然后只对两数的绝对值进行除法运算。所以原码除法的核心其实是在讨论如何对两个正数即绝对值进行除法。2.1 算法基石手工除法的机器化回想一下我们小学学过的竖式除法。计算13 ÷ 3比较13和313大商上4因为3*412最接近且不超过13。用13减去12得到余数1。如果还有小数位我们把余数1后面“拉下来”一个0相当于乘以10变成10继续和3比较。计算机做定点整数除法逻辑完全一样只不过它是在二进制世界里操作并且“拉下来”的不是0而是被除数或余数接下来的位。这个过程可以抽象为以下几步我们以计算两个无符号整数为例初始化将除数和被除数或部分余数对齐。通常我们会把被除数放在一个双倍位宽的寄存器的高位除数放在另一个寄存器。比较与试商将当前的部分余数与除数比较。如果部分余数 除数说明当前商位可以上“1”。如果部分余数 除数则当前商位上“0”。减与移位若商位为1则执行部分余数 部分余数 - 除数。若商位为0则不减相当于减0。然后将部分余数左移一位相当于乘以2并从被除数中“拉下来”一个新的低位补到部分余数的最低位。循环重复步骤2和3直到获得所需精度的所有商位。这个过程清晰直观但有一个关键问题在第二步“比较”时我们实际上已经做了一次减法部分余数-除数来判断大小。如果发现不够减结果为负我们这次减法就白做了因为商位是0我们本不该减。这就引出了最直接的实现方法——恢复余数法。2.2 恢复余数法直白但低效的“笨办法”恢复余数法严格遵循上述手工步骤。它的操作流程如下将部分余数初始为被除数左移一位。用左移后的部分余数减去除数。判断结果如果结果 0说明够减商位设为1新的部分余数就是这次减法的结果。如果结果 0说明不够减商位设为0。并且需要把除数加回去以恢复原来的部分余数。重复步骤1-3直到获得所有商位。为什么叫“恢复”关键就在第3步的“如果结果0”的情况。因为我们在判断时已经执行了余数-除数得到了一个负的中间结果。既然判定商为0意味着这一步不应该执行减法所以我们必须把这个负结果再加上除数让它恢复到减法之前的值然后再进行下一轮的左移。这个“恢复”操作就是一次额外的加法它导致了额外的时钟周期降低了算法效率。实操心得在软件模拟中恢复余数法最容易理解和调试因为它的每一步状态都清晰对应手工计算。你可以打印出每一轮循环后的商、余数状态很容易跟踪错误。但在追求性能的硬件电路或核心循环中它的效率瓶颈非常明显。2.3 加减交替法不恢复余数法聪明的“将错就错”加减交替法是对恢复余数法的优化。它观察到了一个关键规律当出现“不够减”时我们不一定非要恢复原状。让我们分析一下恢复余数法中“不够减”的情况当前部分余数为R(R 0)。左移后变成2R。执行2R - Y(Y是除数)发现结果2R - Y 0。商位q0。恢复操作(2R - Y) Y 2R。然后左移一位变成4R下一轮尝试4R - Y。加减交替法换了一个思路当2R - Y 0时我们不恢复它。我们记下商位q0然后保留这个负的余数R 2R - Y。下一轮我们不是对2R左移而是对这个负的余数R左移然后加上除数Y。即下一轮计算2R Y 2*(2R - Y) Y 4R - Y。神奇的事情发生了这个4R - Y正好是恢复余数法中恢复并左移后再做减法的结果也就是说在恢复余数法中需要“恢复余数-左移-减除数”三步才能达到的状态加减交替法通过“保留负余数-左移-加除数”两步就达到了。加减交替法的规则可以总结为根据上一轮的余数R[i-1]的正负决定本轮操作若R[i-1] 0商位q[i] 1。计算R[i] 2 * R[i-1] - Y。若R[i-1] 0商位q[i] 0。计算R[i] 2 * R[i-1] Y。初始R[0]为被除数视为正数先左移一位并执行R[1] 2*R[0] - Y来启动循环。它的优势在于每一轮循环的操作是固定的要么是“左移减”要么是“左移加”完全取决于上一轮余数的符号而不再需要分支判断后的“恢复”操作。这在硬件实现上非常友好可以构建出更规整、可能更快的电路。踩坑记录在实现加减交替法时最容易出错的地方是对最终余数的处理。因为运算过程中余数可能为负所以循环结束后得到的“最终余数”可能也是负的。如果我们需要一个非负的余数通常如此就需要进行一步校正若最终余数为负则执行余数 余数 除数同时对应的商需要减1。这个校正步骤必须在算法结束时显式进行。3. 补码除法统一符号处理的现代实践原码除法虽然直观但需要单独处理符号。在现代计算机体系结构中带符号整数普遍采用补码表示因为它能让加法和减法的硬件电路统一起来。自然地我们也希望除法运算能直接处理补码数省去额外的符号转换步骤。这就是补码除法的意义。补码除法的目标输入被除数和除数都是补码表示直接输出商和余数的补码。它的算法比原码除法更复杂因为试商的规则不仅取决于数值大小还取决于符号。3.1 补码除法的核心矛盾与规则补码除法的难点在于“试商”。对于正数商位是0或1。但对于补码最高位是符号位商也可能为负当被除数和除数异号时。因此补码除法中的“商位”q_i可以取1或-1在二进制中我们通常用0和1表示但需要理解其代表的实际值。更常见的做法是让商以“偏移”的形式生成最后再调整回标准的补码。一种经典的补码除法算法如 Robertson 算法或其变种规则如下它同样采用加减交替的思想但规则因符号而异符号判断比较被除数余数与除数的符号。同号则执行减法余数 余数 - 除数。异号则执行加法余数 余数 除数。试商根据上一步运算后新的余数的符号决定商位。若新余数与除数同号则商位q[i] 1。若新余数与除数异号则商位q[i] 0。 注意这里的1和0是逻辑值在最终组合成补码商时需要正确解释移位将余数左移一位保持符号位扩展准备下一轮计算。循环与校正重复步骤1-3。算法结束后得到的商可能是“伪商”余数也可能需要校正以符合数学定义被除数 商 * 除数 余数且保证|余数| |除数|余数的符号与被除数相同。3.2 补码除法 vs 原码除法选择与权衡为了更清晰地对比我们来看一个表格特性原码除法补码除法输入/输出格式需将补码数转换为原码绝对值和符号分开处理。直接输入补码直接输出补码。核心操作始终对正数绝对值进行加减和比较。操作依赖于当前余数和除数的符号可能是加也可能是减。试商规则简单基于余数是否大于等于除数。复杂基于余数与除数的符号关系。硬件复杂度相对简单控制逻辑清晰。控制逻辑更复杂需要符号判断电路。速度恢复余数法较慢加减交替法较快。与加减交替法类似但每步的符号判断可能引入额外延迟。适用场景在早期硬件或对电路 simplicity 要求高的设计中常见软件实现易于理解。在现代通用CPU的整数除法单元中更常见与补码加法器/减法器统一无需前端转换。如何选择如果你在软件中实现一个定点数运算库我通常会推荐先使用原码的加减交替法。理由是实现相对简单调试方便并且你可以先处理符号核心运算单元只处理正数逻辑清晰不易出错。性能在软件层面差异不大。如果你在设计硬件电路如FPGA并且你的数据通路本身就是补码那么直接实现补码除法可能更优因为它避免了输入输出时的格式转换开销能与数据通路无缝衔接。对于大多数嵌入式C程序员你可能不需要从零实现这些算法。编译器如GCC在为目标芯片生成没有硬件除法指令的代码时例如某些ARM Cortex-M0内核会自动调用内置的运行时库函数如__aeabi_idiv这些库函数已经用高度优化的汇编实现了类似算法。你的价值在于理解其原理以便在调试、优化或需要特殊舍入模式时知道底层发生了什么。4. 从理论到实践一个定点除法库的实现要点理解了算法我们来看看如何把它们封装成一个实用的定点数除法函数。假设我们使用Q格式表示定点数例如Q151位符号位15位小数位。4.1 定标与溢出最关键的预处理定点除法的最大陷阱是溢出和精度损失。整数除法A/B结果的范围可能远大于A或B。在定点数中我们通过调整结果的“定标点”来管理这个问题。定标规则 对于两个定点数A(Qm.n格式) 和B(Qp.q格式)它们的除法C A / B。理论上C的小数位位数等于A的小数位 - B的小数位。但为了在有限的字长如32位内保留尽可能多的精度并防止溢出通常采用先提升精度再计算的策略。一个常见的实践是将被除数A提升到双倍精度例如从32位提升到64位。将这个双倍精度的被除数左移n位n是预设的结果小数位或B的小数位。用这个左移后的64位数除以除数B。得到的64位商取其合适的部分作为最终的32位结果。为什么左移左移相当于乘以2^n。因为整数除法会截断小数部分我们先将被除数放大再做除法就能在整数结果中保留更多原来小数部分的信息。这类似于计算(A * 2^n) / B。// 伪代码示例Q15格式的定点除法 (A/B) int32_t q15_div(int32_t A_q15, int32_t B_q15) { // 防止除以零 if (B_q15 0) { return (A_q15 0) ? INT32_MAX : INT32_MIN; // 返回饱和值 } // 将被除数提升到64位并左移15位因为Q15有15个小数位 int64_t dividend (int64_t)A_q15 15; // 执行64位除以32位的整数除法 int64_t quotient dividend / B_q15; // 检查结果是否在32位Q15格式的范围内并进行饱和处理 if (quotient INT32_MAX) quotient INT32_MAX; if (quotient INT32_MIN) quotient INT32_MIN; return (int32_t)quotient; }重要提示上面的代码使用了原生的整数除法/。在没有硬件除法指令的平台上这个/操作会触发编译器调用我们前面讨论的那些底层除法算法库。我们这里展示的是定标和防溢出的逻辑。4.2 舍入策略不仅仅是截断整数除法天然是向零截断Truncate toward zero。但在很多信号处理或控制应用中我们需要更精确的舍入比如四舍五入Round to nearest。如何实现四舍五入的定点除法核心思想是在除法之前给被除数加上一个“舍入项”。这个舍入项通常是除数 / 2。如果结果是正数(A B/2) / B实现了四舍五入。需要注意处理负数的情况以保证对称性。一种通用的方法是((A ^ B) 0) ? (A B/2) : (A - B/2)然后再除以B。即根据符号位决定是加还是减二分之一除数。// 带四舍五入的Q15除法 int32_t q15_div_round(int32_t A_q15, int32_t B_q15) { if (B_q15 0) { /* 处理除零 */ } int64_t dividend (int64_t)A_q15 15; int64_t rounding (B_q15 0) ? (B_q15 1) : -( (-B_q15) 1); // B/2注意负数的处理 // 判断A和B是否同号决定加或减 rounding if ((A_q15 ^ B_q15) 0) { dividend rounding; } else { dividend - rounding; } int64_t quotient dividend / B_q15; // 饱和处理 return saturate_q15(quotient); }4.3 性能优化与特殊值处理性能优化查表法对于除数范围有限且精度要求不极高的场景如某些颜色空间转换可以预先计算好1/B的倒数表将除法转化为乘法A * (1/B)。乘法比除法快得多。牛顿迭代法用于求解倒数1/B通过几次乘法和减法迭代就能得到高精度的倒数近似值然后再做乘法。这在GPU和高性能计算中很常见。利用硬件指令如果CPU有硬件除法指令直接使用。如果有单指令多数据SIMD除法指令则批量处理。特殊值处理 一个健壮的库必须处理边界情况除数为零返回饱和值最大值或最小值或抛出异常根据系统要求决定。溢出在定标和计算过程中持续检查。例如在左移被除数前检查它是否已经超过64位容量的有效范围。最小负数除以-1在补码表示中比如32位有符号数INT32_MIN / -1的结果应该是-INT32_MIN但这个值超出了INT32_MAX会导致溢出。必须单独处理返回饱和值。5. 调试与验证如何确保你的定点除法正确无误自己实现了一套除法逻辑后如何验证它是对的尤其是处理各种边界情况和负数时。1. 穷举测试针对小位宽如果你的定点数位宽较小比如8位或16位完全可以写一个测试程序遍历所有可能的被除数和除数组合跳过除数为零将你的定点除法结果与浮点数结果进行对比。计算误差确保在允许的精度范围内例如对于Q格式误差应小于1个最低有效位。2. 随机测试与边界测试对于32位等较大位宽穷举不现实。可以采用大规模随机测试生成几百万组随机数进行对比。定向边界测试专门测试INT_MAX, INT_MIN, 1, -1, 0等边界值及其组合。例如INT_MIN / 1,INT_MAX / -1,1 / INT_MIN等。3. 与参考实现交叉验证如果你是用C语言实现可以先用原生double类型计算一个高精度结果作为参考。或者使用另一个你信任的、经过验证的定点数学库如ARM的CMSIS-DSP库的结果进行对比。4. 打印中间状态对于恢复余数法或加减交替法在调试时把每一轮循环的商位、余数值都打印出来。然后手工演算几步看是否吻合。这是理解算法和定位错误最有效的方法。一个常见的验证陷阱余数的符号。务必验证你的算法满足定点除法的数学定义被除数 商 * 除数 余数并且|余数| |除数|。对于有符号除法余数的符号应该等于被除数的符号或为0。这是检验补码除法实现是否正确的重要标准。很多自己实现的算法最后算出来的余数符号是错的就是因为校正步骤没做好。实现定点除法的过程是一次对计算机底层运算逻辑的深刻巡礼。从原码到补码从恢复余数到加减交替每一步优化都体现了在硬件约束下追求效率和精度的智慧。虽然现在很多场景下我们可以直接依赖硬件或编译器但掌握这些原理能让你在遇到性能瓶颈、精度问题或需要在非常规平台上编程时拥有从底层解决问题的能力。下次当你在没有FPU的芯片上编写控制算法时希望这些关于“如何用整数做除法”的细节能帮你写出既高效又可靠的代码。