这里的目标是找到以小端表示法存储的两个 16 位数字的 GCD。这些数字存储在以下存储单元中:
- 第一个数字:0x3000-0x3001
- 秒数:0x4000-0x4001
- 结果应为:0x5000-0x5001
以下示例适用于 8 位数字:
ORG 0000H
MOV 30H, #09
MOV 40H, #06
MOV A, 30H
MOV B, 40H
CJNE A, B, next
LJMP stop
next:
JNC loop
MOV A, R2
MOV B, R1
loop:
MOV R3, B
DIV AB
MOV A, R3
MOV R7, B
CJNE R7, #00H, loop
stop:
MOV 50H, A
END
问题:如何修改此代码以对两个 16 位数字进行操作？我是否需要对各个字节进行操作，然后使用数据指针 (DPTR) 将它们加载/移动到所需的存储单元？
(我正在使用 µVision IDE)
最佳答案
计算最大公约数的一种方法是使用 Euclid's algorithm 。要获得两个 16 位数字的 GCD，需要扩展 8051 上非常有限的 DIV AB。这并非不可能，但我选择使用一种不需要除法的算法全部。
二值GCD算法
我们可以避免 8051 有限的除法能力，并使用一种通过一系列移位和减法来代替模计算的算法。下面是Binary GCD algorithm的方法看起来像 BASIC:
Procedure BinaryGCD
; Calculates R% = GCD(A%,B%)
If A%=0 Or B%=0 Then
R% = 1
Else
C% = 0
While Even(A%) And Even(B%)
Inc C%
A% = Shr(A%,1)
B% = Shr(B%,1)
Wend
Do
While Even(A%)
A% = Shr(A%,1)
Wend
While Even(B%)
B% = Shr(B%,1)
Wend
Exit If A%=B%
If A%>B% Then
Sub A%,B%
Else
Sub B%,A%
Endif
Loop
R% = Shl(A%,C%)
Endif
Return
实现说明
外部存储器中存储的数字被复制到内部存储器中的位地址区。为什么是这样？使用内部存储器可以避免必须一直操作 16 位地址的麻烦。特别使用位地址区域，可以编写有效的代码来测试偶数/奇数条件。在位地址区域之外存储将需要更多字节和更多周期，更不用说它会破坏累加器。比较:
; Multiprecision number starts at 58h (not bit addressable)
MOV A, #1
ANL A, 58h
JNZ IsOdd
; Uses 6 bytes and consumes 4 cycles
; Multiprecision number starts at 28h (bit addressable)
JB 64, IsOdd
; Uses 3 bytes and consumes 2 cycles
请注意，我的程序可以处理从字节到 qword 以及之间的所有内容的无符号多精度数字。我首先创建了一系列方便的子例程来处理多字节数字。其中许多子例程被调用一次，因此也可以轻松内联。为了生成可读的程序，我选择不这样做。
子例程
IN()
对于每个子例程，R0、R1 和 DPTR 寄存器在输入时都是指向所涉及数字开头的指针(自此以来的最低有效字节)这是小端字节序)。
OUT()
从mpLoad和mpStore返回时，R1和DPTR都将提前，以便能够处理相邻项目，而无需必须重新加载指针寄存器。
从 mpTest 返回时，累加器 A 很重要。如果 A 为零，则提交的数量为零。
从 mpCmp 返回时，累加器 A 和进位标志 C 非常重要。如果 A 为零，则提交的数字彼此相等。否则，清晰的 C 表示第一个数字 (@R0) 大于第二个数字 (@R1)，反之亦然一套C。
MOD()
这里列出了子例程使用但不返回记录值的所有寄存器。
; Copies a multiprecision number from external memory to internal memory
; IN(R1,DPTR) OUT(R1,DPTR) MOD(A,R2)
mpLoad:
MOV R2, #MPC
Load:
MOVX A, @DPTR
MOV @R1, A
INC DPTR
INC R1
DJNZ R2, Load
RET
; Copies a multiprecision number from internal memory to external memory
; IN(R1,DPTR) OUT(R1,DPTR) MOD(A,R2)
mpStore:
MOV R2, #MPC
Store:
MOV A, @R1
MOVX @DPTR, A
INC DPTR
INC R1
DJNZ R2, Store
RET
; Doubles a multiprecision number
; IN(R1) OUT() MOD(A,R1,R2)
mpShl:
MOV R2, #MPC
CLR C
Shl:
MOV A, @R1
RLC A
MOV @R1, A
INC R1
DJNZ R2, Shl
RET
; Halves a multiprecision number
; IN(R1) OUT() MOD(A,R2)
mpShr:
MOV R2, #MPC
MOV A, R1
ADD A, R2 ; -> C == 0
MOV R1, A
Shr:
DEC R1
MOV A, @R1
RRC A
MOV @R1, A
DJNZ R2, Shr
RET
; Tests if a multiprecision number is zero
; IN(R1) OUT(A) MOD(R1,R2)
mpTest:
MOV R2, #MPC
MOV A, #0
Test:
ORL A, @R1
INC R1
DJNZ R2, Test
RET
; Compares two multiprecision numbers
; IN(R0,R1) OUT(A,C) MOD(R0,R1,R2)
mpCmp:
MOV R2, #MPC
MOV A, R1
ADD A, R2
MOV R1, A
MOV A, R0
ADD A, R2 ; -> C == 0
MOV R0, A
Cmp:
DEC R0
DEC R1
MOV A, @R0
SUBB A, @R1
JNZ CmpRet
DJNZ R2, Cmp
CmpRet:
RET
; Subtracts two multiprecision numbers
; IN(R0,R1) OUT() MOD(A,R0,R1,R2)
mpSub:
MOV R2, #MPC
CLR C
Sub:
MOV A, @R0
SUBB A, @R1
MOV @R0, A
INC R0
INC R1
DJNZ R2, Sub
RET
主要代码
您可以轻松地将其变成一个成熟的程序。
MPC EQU 2 ; Number of bytes per number aka precision
NumX EQU 20h ; Internal memory storage address for first number
NumY EQU 28h ; Internal memory storage address for second number
; -------------------------
MOV R1, #NumX
MOV DPTR, #3000h ; External memory storage address for first number
LCALL mpLoad
MOV R1, #NumY
MOV DPTR, #4000h ; External memory storage address for second number
LCALL mpLoad
; -------------------------
MOV R3, #MPC
MOV R0, #NumX
MOV R1, #NumX
LCALL mpTest ; -> A
JZ SetOne
MOV R1, #NumY
LCALL mpTest ; -> A
JNZ Begin
SetOne:
INC A ; 0 -> 1, 255 -> 0, 255 -> 0, ...
MOV @R0, A
MOV A, #255
INC R0
DJNZ R3, SetOne
SJMP Copy
; -------------------------
Begin:
MOV R3, #0 ; Bits
While1:
JB 0, While3 ; Jump if NumX[bit0] == 1
JB 64, While2 ; Jump if NumY[bit0] == 1
INC R3 ; Bits++
MOV R1, #NumX
LCALL mpShr ; X >> 1
MOV R1, #NumY
LCALL mpShr ; Y >> 1
SJMP While1
; -------------------------
While2:
JB 0, While3 ; Jump if NumX[bit0] == 1
MOV R1, #NumX
LCALL mpShr ; X >> 1
SJMP While2
; - - - - - - - - - - - - -
While3:
JB 64, Compare ; Jump if NumY[bit0] == 1
MOV R1, #NumY
LCALL mpShr ; Y >> 1
SJMP While3
; - - - - - - - - - - - - -
Compare:
MOV R0, #NumX
MOV R1, #NumY
LCALL mpCmp ; -> A C
JZ Equal
MOV R0, #NumX
MOV R1, #NumY
JNC Minus ; Do (X - Y)
MOV R0, #NumY
MOV R1, #NumX
Minus:
LCALL mpSub ; Did (X - Y) or (Y - X)
SJMP While2
; -------------------------
Equal:
MOV A, R3 ; Bits
JZ Copy
Scale: ; X << Bits
MOV R1, #NumX
LCALL mpShl ; X << 1
DJNZ R3, Scale
; -------------------------
Copy:
MOV R1, #NumX
MOV DPTR, #5000h ; External memory storage address for resulting number
LCALL mpStore
; -------------------------
EXIT:
NOP
SJMP $
; Here you add the subroutines
END
关于assembly - 两个 16 位数字的 GCD(最大公约数)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/65480973/