我可以帮你翻译成中文。您在哪里可以找到软件乘法和除法算法？

Question

我正在使用没有硬件乘除器的微控制器。我需要编写这些基本操作的软件算法，以便在紧凑和高效之间取得良好平衡。我的C编译器端口将采用这些算法，而不是由C开发人员自己编写。

目前我的谷歌搜索结果大多噪音干扰。

有人能向我指出一些有用信息吗？我可以使用加/减和移位指令。基于查找表的算法也可能适合我，但我有些担心将其全部压缩进编译器的后端...恕我直言。

- srking

---

这是一种奇怪的微控制器吗？难道还没有为它开发C编译器吗？你可以使用该编译器（可能是个好主意），或者如果有源代码可用，检查其例程。 - Carl Norum

这个微控制器有名字吗？ - AakashM

这是新的。它是一个研究项目的一部分。 - srking

@Carl 特别提醒，原帖作者应该查看 libgcc，因为 GCC 的软件乘除是在那里实现的。 http://gcc.gnu.org/onlinedocs/gccint/Integer-library-routines.html - ephemient

+1 提到了libgcc，但代码很难读。 - Richard Pennington

Answer 1

这是一个简单的乘法算法：

1. 从乘数的最右边开始。
2. 如果乘数中的位是1，则加上被乘数。
3. 将被乘数向左移动1位。
4. 移到乘数的下一位并返回步骤2。

这是一个除法算法：

1. 如果除数大于被除数，则停止。
2. 在除数寄存器小于被除数寄存器时，向左移位。
3. 将除数寄存器向右移1位。
4. 用除数寄存器减去被除数寄存器，并在结果寄存器中将对应于所做移位总数的位更改为1。
5. 回到步骤1，除数寄存器处于原始状态。

当然，您需要加入防止除以0的检查，但它应该可以工作。

这些算法当然只适用于整数。

- Justin Peel

---

如果您将(1<<n)+1除以(1<<x)，其中n是寄存器宽度-1，那么在除法算法的第3步会发生什么？ - user14554

@jbcreix，我不确定我理解你在问什么。你能详细说明一下吗？ - Justin Peel

如果在被除数较大的情况下将除数向左移位，最高位将在非常大的被除数中被移出。因此，在除数为2的幂的情况下向右移位时，您将得到一个不同的数字0。 - user14554

@jbcreix，当然，你必须小心避免溢出问题。 - Justin Peel

Answer 2

以下是关于IT技术的参考资料，我最喜欢的书籍：

http://www.hackersdelight.org/

此外，《计算机程序设计艺术》也是不错的选择：http://www-cs-faculty.stanford.edu/~uno/taocp.html

- Johan Kotlinski

Answer 3

事实证明，我仍然有一些旧的68000汇编代码用于长乘法和长除法。 68000代码非常干净简单，因此应该很容易为您的芯片进行翻译。

如果我没记错的话，68000有乘法和除法指令-我认为这些是作为学习练习编写的。

决定将代码放在这里。添加了注释，并在此过程中解决了一个问题。

;
; Purpose  : division of longword by longword to give longword
;          : all values signed.
; Requires : d0.L == Value to divide
;          : d1.L == Value to divide by
; Changes  : d0.L == Remainder
;          : d2.L == Result
;          : corrupts d1, d3, d4
;

        section text

ldiv:   move    #0,d3     ; Convert d0 -ve to +ve - d3 records original sign
        tst.l   d0
        bpl.s   lib5a
        neg.l   d0
        not     d3
lib5a:  tst.l   d1        ; Convert d1 -ve to +ve - d3 records result sign
        bpl.s   lib5b
        neg.l   d1
        not     d3
lib5b:  tst.l   d1        ; Detect division by zero (not really handled well)
        bne.s   lib3a
        rts
lib3a:  moveq.l #0,d2     ; Init working result d2
        moveq.l #1,d4     ; Init d4
lib3b:  cmp.l   d0,d1     ; while d0 < d1 {
        bhi.s   lib3c
        asl.l   #1,d1     ; double d1 and d4
        asl.l   #1,d4
        bra.s   lib3b     ; }
lib3c:  asr.l   #1,d1     ; halve d1 and d4
        asr.l   #1,d4
        bcs.s   lib3d     ; stop when d4 reaches zero
        cmp.l   d0,d1     ; do subtraction if appropriate
        bhi.s   lib3c
        or.l    d4,d2     ; update result
        sub.l   d1,d0
        bne.s   lib3c
lib3d:                    ; fix the result and remainder signs
;       and.l   #$7fffffff,d2  ; don't know why this is here
        tst     d3
        beq.s   lib3e
        neg.l   d2
        neg.l   d0
lib3e:  rts

;
; Purpose  : Multiply long by long to give long
; Requires : D0.L == Input 1
;          : D1.L == Input 2
; Changes  : D2.L == Result
;          : D3.L is corrupted
;

lmul:   move    #0,d3       ; d0 -ve to +ve, original sign in d3
        tst.l   d0
        bpl.s   lib4c
        neg.l   d0
        not     d3
lib4c:  tst.l   d1          ; d1 -ve to +ve, result sign in d3
        bpl.s   lib4d
        neg.l   d1
        not     d3
lib4d:  moveq.l #0,d2       ; init d2 as working result
lib4a:  asr.l   #1,d0       ; shift d0 right
        bcs.s   lib4b       ; if a bit fell off, update result
        asl.l   #1,d1       ; either way, shift left d1
        tst.l   d0
        bne.s   lib4a       ; if d0 non-zero, continue
        tst.l   d3          ; basically done - apply sign?
        beq.s   lib4e       ; was broken! now fixed
        neg.l   d2
lib4e:  rts
lib4b:  add.l   d1,d2      ; main loop body - update result
        asl.l   #1,d1
        bra.s   lib4a

顺便说一句 - 我从来没有弄清楚在开始时是否有必要将所有东西转换为正数。如果你在移位操作上小心谨慎，这可能是可以避免的额外开销。

- user180247

Answer 4

这是一个除法算法：http://www.prasannatech.net/2009/01/division-without-division-operator_24.html 我假设我们谈论的是整数？

如果没有硬件支持，你将不得不实现自己的除以零异常。

（我没有很快找到乘法算法，但如果其他人没有找到，我会继续寻找）。

- Seth

---

维基百科描述了许多乘法算法 - 移位和加法是最简单的。http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add - Carl Norum

Answer 5

一个简单而相当高效的整数乘法算法是俄罗斯农民乘法。

对于有理数，您可以尝试使用二进制引号表示法，其中除法比通常更容易。

- outis

---

我认为算法是为人类而不是机器设计的。 - user180247

算法与处理器无关。 - outis

不一定 - 一个算法的表现可能比其他算法更好或更差，这取决于它运行的硬件是否支持正确的基本操作。人脑支持与 CPU 不同的基本操作。例如，我的个人大脑的 32 位整数加法至少比 x86 慢几十亿倍，而我拥有硬件加速的视觉算法，远远优于任何当前的个人电脑。 - user180247

既然“除以2并且舍去余数”就是“右移”，而“测试奇偶性”就是“逻辑与1并测试是否等于0”，因此它似乎可以很好地映射到基本的CPU操作上。这本质上就是Justin答案中描述的相同算法。 - caf

@Steve314：你说得对，算法效率取决于基本操作的效率，而这些操作又与处理器有关，但算法的正确性与处理器无关。从这个意义上说，俄罗斯农民乘法并不是为了任何特定的处理器。正如caf所指出的那样，俄罗斯农民乘法在CPU上效率很高。 - outis

@caf：是的。这里发布的所有特定乘法算法本质上都是相同的。 - outis

Answer 6

Microchip的PICmicro 16Fxxx系列芯片没有乘除指令。 也许它的一些软件乘法和软件除法例程可以移植到您的MCU。

PIC 微控制器基本数学乘法方法

PIC 微控制器基本数学除法方法

还可以查看“牛顿法进行除法运算”。 我认为这种方法给出了任何我见过的除法算法中最小的可执行大小，尽管解释使它听起来比它实际上更复杂。 我听说一些早期的Cray超级计算机使用牛顿法进行除法运算。

- David Cary

Answer 7

要进行乘法运算，需要将移位后的被乘数的部分积加到累加器中，当且仅当乘数对应的比特位为1时。在循环结束时，将被乘数和乘数进行移位，并测试乘数 & 1，以确定是否需要进行加法运算。

- Arthur Kalliokoski