我的阶乘程序出现奇怪问题
Strange issue with my factorial program
我决定学习 x86 汇编作为我的第一门正式编程语言。
我决定编写一个程序来计算给定数字的阶乘。
代码在任何大于 12 的情况下都可以正常工作！，之后我得到不正确的结果。
我怀疑是因为结果大于 32 位。正确吗？
为了更正这个问题，我尝试 rcl edx 寄存器。
15个！应该是 1307674368000 但是，它 returns 27701857280.
.386
.model flat, stdcall
option casemap :none
includelib \masm32\lib\msvcrt.lib
sprintf proto C :vararg
includelib \masm32\lib\user32.lib
MessageBoxA proto :ptr,:ptr,:ptr,:DWORD
includelib \masm32\lib\kernel32.lib
ExitProcess proto :dword
.data
format db "%lld", 13, 10, 0
_title db "Result",13,10,0
.code
main PROC
LOCAL szBuf[9]:byte
xor edx,edx
rcl edx ,1
xor ebx,ebx
mov eax, 15 ; start of 15!
mov ebx,eax ; Prepares # of loop counter cycle
factoral:
dec ebx ;loop counter
jz ready ;when ebx = 0 jump to ready step
imul eax, ebx ; Multiply for intermeddiate result.
rcl edx, 1 ; Shift carry flag to edx to handle > 32 bit results.
jnz factoral ; Continue loop counter when ebx > 0
ready:
invoke sprintf, addr szBuf, offset format, eax, edx
invoke MessageBoxA, 0, addr szBuf, offset _title, 0
invoke ExitProcess, 0
main ENDP
END main
额外：使用 shl eax, 1 计算中间的第二度部分 (n*2) 是否比使用 imul 计算每个度更好。
示例：5！
1) (5*4 =20)
2) (20*3 = 60)
3)(60位左移1次=120)
4) (120 * 1 = 120)
I suspect It is due to the result being larger than 32 bits. Correct?
没错。 12！ == 479,001,600，可以用 32 位来表示（作为无符号数，但这只是解释，而不是表示）。然而，13！ == 6,227,020,800，溢出 32 位。如果您使用的计算器可以显示二进制数的表示形式（Windows、macOS 和大多数 Linux 台式机都内置了这样的程序员计算器），您会看到 64 -bit 表示设置了第 32 位。显然，如果你总共只有 32 位，它会溢出！
关于您的代码，我不清楚您希望 RCL 在这里做什么是有用的。该指令基本上是通过进位标志 (CF) 进行循环。它将 CF 移入最低有效位 (LSB)，同时将最高有效位 (MSB) 移入 CF。英特尔架构手册对此有一个漂亮的描述，可能更清楚：
我看不出有任何方法可以帮助您处理大于 32 位的值。我的意思是， 是 是真的 IMUL 设置 CF 当乘法导致一个位被带入结果的上半部分时，但旋转不会神奇地允许您在 32 位寄存器中表示 64 位数量。 （如果这种旋转能让你得到正确的结果，大概英特尔会把它作为乘法的一部分来做？）
是一条指令，您可以使用它来获得 32 位乘法的 64 位乘积。它也有 IMUL 助记符，但它是只采用一个操作数的形式：
IMUL r/m32
这会将 EAX（硬编码）乘以指定的操作数（r/m32，这意味着 32 位寄存器或从内存位置读取的 32 位值），将64 位 结果为 EDX:EAX（也是硬编码）。请注意，EDX:EAX 表示法表示高位在 EDX 中，低位在 EAX 中。这是在 32 位 x86 架构上表示 64 位值的标准约定。
因此，对代码的简单修复是：
mov eax, 13 ; initial value
mov ecx, eax ; loop counter
Factorial:
dec ecx ; decrement counter
jz Finished ; when counter == 0, we're done
imul ecx ; multiply by counter (EDX:EAX = EAX * ECX)
jmp Factorial ; go back to top of loop
Finished:
...
请注意，我使用 ECX 作为计数器，而不是 EBX，因为这更符合习惯。 真的 你使用哪个寄存器并不重要，除非指令使用像 IMUL 这样的硬编码寄存器，但是当它可用时，通常使用 ECX一个柜台。 （这是它最初的目的。）此外，当您开始与 C/C++ 代码进行互操作时，您需要注意调用约定，其中 EAX、ECX 和EDX 是您的过程可以破坏的寄存器，而您应该保存和恢复其他寄存器的原始值。这意味着避免使用 EBX 除非你绝对需要它可以节省一些代码。
此外，您不需要在初始化之前清除寄存器。因此，代码如下：
xor ebx,ebx
...
mov ebx,eax ; Prepares # of loop counter cycle
是silly/unnecessary。只需执行 MOVe.
哦，还有这段代码：
jnz factoral ; Continue loop counter when ebx > 0
从来没有用过。您试图使用由初始 dec ebx 设置的零标志 (ZF)，但其他干预指令破坏了标志，因此您没有读取正确的标志值。您需要立即对 EBX 进行 比较，才能设置标志。
无论如何，在此代码的末尾，您将在 Finished 处结束，阶乘将在 EDX:EAX.
中
但是，这只适用于 13!。之后，它将失败。为什么？因为IMUL只用EAX作为它的被乘数，而不是EDX:EAX。 13×12×11×10×9×8×7×6×5×4×3的乘积正好在EAX，然后乘以2，乘积在EDX:EAX.但是如果你尝试做 15!，你会更早地溢出到 EDX:EAX，但是 EDX 会被后续的乘法忽略。
因此，您需要变得更聪明并编写实际执行完整 64 位乘法的代码，即，将 64 位被乘数乘以 32 位乘数以获得 64 位乘积。
幸运的是，这并不困难，尤其是，因为根据定义，阶乘仅取非负值，因此我们无需担心负数.换句话说，我们只需要做一个无符号乘法。
顺便说一下，您的 printf 格式字符串应该是 "%llu"，因为结果应该被解释为 unsigned 数量。
此代码为：
; EAX = divisor
; ECX = high bits of dividend
; EDX = low bits of dividend
imul ecx, eax ; multiply high bits of multiplicand by multiplier, quotient in ECX
mul edx ; multiply low bits of multiplicand by multiplier, quotient in EDX:EAX
add edx, ecx ; add high-order product to high bits of low-order product
; EDX:EAX = product
最后一条评论的措辞有点毛茸茸……希望代码能直观理解。我们所做的就是将乘法分成两部分，分别对 64 位值的 32 位部分进行运算，然后将结果相加。
将此乘法代码集成到您的原始代码中，我们得到如下内容：
;push ebx ; save EBX (only needed if complying with C calling convention)
mov eax, 15 ; initial value (low-order bits)
xor edx, edx ; initial value's high-order bits are 0
mov ecx, eax ; loop counter
Factorial:
dec ecx ; decrement counter
jz Finished ; when counter == 0, we're done
mov ebx, ecx ; make copy of counter
imul ebx, edx ; high-order bits * multiplier
mul ecx ; low-order bits * multiplier
add edx, ebx ; add high-order product to high-order bits of low-order product
jmp Factorial ; go back to top of loop
Finished:
;pop ebx ; restore EBX (only needed if complying with C calling convention)
...
这很有效！至少，它一直工作到 20！。在 21!，由于我们的老朋友溢出，你得到了错误的结果。 21！不适合 64 位值。
它对 0 也不起作用！—你得到的不是数学定义的结果 1，而是 0。你应该能够插入必要的比较和分支来自己解决这个问题。
有一些方法可以进一步优化这段代码，但代价是引入额外的复杂性，所以确保你首先理解这一点！
我已经提到的一个优化是确保你不做最终乘以 1。这只需要在循环体的末尾插入一个额外的比较：
;push ebx ; save EBX (only needed if complying with C calling convention)
mov eax, 15 ; initial value (low-order bits)
xor edx, edx ; initial value's high-order bits are 0
mov ecx, eax ; loop counter
Factorial:
dec ecx ; decrement counter
jz Finished ; when counter == 0, we're done
mov ebx, ecx ; make copy of counter
imul ebx, edx ; high-order bits * multiplier
mul ecx ; low-order bits * multiplier
add edx, ebx ; add high-order product to high-order bits of low-order product
cmp ecx, 1
jg Factorial ; keep looping as long as counter > 1
Finished:
;pop ebx ; restore EBX (only needed if complying with C calling convention)
...
您可以通过将初始比较提升到循环之外来稍微改进一下：
;push ebx ; save EBX (only needed if complying with C calling convention)
mov eax, 15 ; initial value (low-order bits)
xor edx, edx ; initial value's high-order bits are 0
mov ecx, eax ; loop counter
dec ecx ; decrement counter
jz Finished ; when counter == 0, we're done, so skip the loop
Factorial:
mov ebx, ecx ; make copy of counter
imul ebx, edx ; high-order bits * multiplier
mul ecx ; low-order bits * multiplier
add edx, ebx ; add high-order product to high-order bits of low-order product
dec ecx ; decrement counter
jg Factorial ; keep looping as long as counter > 1
Finished:
;pop ebx ; restore EBX (only needed if complying with C calling convention)
...
并且通过简单的优化就可以做到这一点。对于其他想法，您可以 explore what C compilers emit for similar code，但请注意，此代码的大部分内容都非常重要。 （GCC 6.3 的输出看起来很像我的代码，但 GCC 7.1 展开循环以提高速度，但导致代码更加混乱和复杂 read/understand。）除此之外，还要注意 C 编译器不必须有完美的优化器！通常情况下，专业的汇编程序员可以编写比编译器生成的代码更优化的代码（尽管他们不能那么快！）。
Extra: Would using shl eax, 1 to calculate the 2nd degree portion (n*2) for the intermediate be better than using imul for each and every degree.
没有
首先，你真的不想写 shl reg, 1 除非你真的需要设置进位标志。左移 1 相当于乘以 2，相当于将值加到自身上。所以，add reg, reg 更简单、更好、更快。
但是，在这种情况下，即使那样也不会更好。虽然简单的移位或加法确实通常比乘法快（但是 —), the only way you could use it here inside the loop is if you first checked to see that you were supposed to be multiplying by 2, and the cost of doing that check (more specifically, the cost of making the decision as a result of that check) is far more costly than a simple integer multiplication. Why? Because the decision requires a branch, which introduces the possibility of 。即使你 只有 在乘数 == 2 的情况下预测错误，这将比 IMUL 和 SHL/ADD.
之间的差异更昂贵
不过，事实上，我们可以对每个 2 的幂进行 shl reg, x 运算——这样会更快吗？不，出于同样的原因。实际上，更糟的是，因为它会 增加 错误预测的机会。条件会按照分支预测算法不太可能理解的模式交替出现，从而导致错误预测。
我决定学习 x86 汇编作为我的第一门正式编程语言。
我决定编写一个程序来计算给定数字的阶乘。
代码在任何大于 12 的情况下都可以正常工作！，之后我得到不正确的结果。
我怀疑是因为结果大于 32 位。正确吗？
为了更正这个问题，我尝试 rcl edx 寄存器。
15个！应该是 1307674368000 但是，它 returns 27701857280.
.386
.model flat, stdcall
option casemap :none
includelib \masm32\lib\msvcrt.lib
sprintf proto C :vararg
includelib \masm32\lib\user32.lib
MessageBoxA proto :ptr,:ptr,:ptr,:DWORD
includelib \masm32\lib\kernel32.lib
ExitProcess proto :dword
.data
format db "%lld", 13, 10, 0
_title db "Result",13,10,0
.code
main PROC
LOCAL szBuf[9]:byte
xor edx,edx
rcl edx ,1
xor ebx,ebx
mov eax, 15 ; start of 15!
mov ebx,eax ; Prepares # of loop counter cycle
factoral:
dec ebx ;loop counter
jz ready ;when ebx = 0 jump to ready step
imul eax, ebx ; Multiply for intermeddiate result.
rcl edx, 1 ; Shift carry flag to edx to handle > 32 bit results.
jnz factoral ; Continue loop counter when ebx > 0
ready:
invoke sprintf, addr szBuf, offset format, eax, edx
invoke MessageBoxA, 0, addr szBuf, offset _title, 0
invoke ExitProcess, 0
main ENDP
END main
额外：使用 shl eax, 1 计算中间的第二度部分 (n*2) 是否比使用 imul 计算每个度更好。
示例：5！
1) (5*4 =20)
2) (20*3 = 60)
3)(60位左移1次=120)
4) (120 * 1 = 120)
I suspect It is due to the result being larger than 32 bits. Correct?
没错。 12！ == 479,001,600，可以用 32 位来表示（作为无符号数，但这只是解释，而不是表示）。然而，13！ == 6,227,020,800，溢出 32 位。如果您使用的计算器可以显示二进制数的表示形式（Windows、macOS 和大多数 Linux 台式机都内置了这样的程序员计算器），您会看到 64 -bit 表示设置了第 32 位。显然，如果你总共只有 32 位，它会溢出！
关于您的代码，我不清楚您希望 RCL 在这里做什么是有用的。该指令基本上是通过进位标志 (CF) 进行循环。它将 CF 移入最低有效位 (LSB)，同时将最高有效位 (MSB) 移入 CF。英特尔架构手册对此有一个漂亮的描述，可能更清楚：
我看不出有任何方法可以帮助您处理大于 32 位的值。我的意思是， 是 是真的 IMUL 设置 CF 当乘法导致一个位被带入结果的上半部分时，但旋转不会神奇地允许您在 32 位寄存器中表示 64 位数量。 （如果这种旋转能让你得到正确的结果，大概英特尔会把它作为乘法的一部分来做？）
是一条指令，您可以使用它来获得 32 位乘法的 64 位乘积。它也有 IMUL 助记符，但它是只采用一个操作数的形式：
IMUL r/m32
这会将 EAX（硬编码）乘以指定的操作数（r/m32，这意味着 32 位寄存器或从内存位置读取的 32 位值），将64 位 结果为 EDX:EAX（也是硬编码）。请注意，EDX:EAX 表示法表示高位在 EDX 中，低位在 EAX 中。这是在 32 位 x86 架构上表示 64 位值的标准约定。
因此，对代码的简单修复是：
mov eax, 13 ; initial value
mov ecx, eax ; loop counter
Factorial:
dec ecx ; decrement counter
jz Finished ; when counter == 0, we're done
imul ecx ; multiply by counter (EDX:EAX = EAX * ECX)
jmp Factorial ; go back to top of loop
Finished:
...
请注意，我使用 ECX 作为计数器，而不是 EBX，因为这更符合习惯。 真的 你使用哪个寄存器并不重要，除非指令使用像 IMUL 这样的硬编码寄存器，但是当它可用时，通常使用 ECX一个柜台。 （这是它最初的目的。）此外，当您开始与 C/C++ 代码进行互操作时，您需要注意调用约定，其中 EAX、ECX 和EDX 是您的过程可以破坏的寄存器，而您应该保存和恢复其他寄存器的原始值。这意味着避免使用 EBX 除非你绝对需要它可以节省一些代码。
此外，您不需要在初始化之前清除寄存器。因此，代码如下：
xor ebx,ebx
...
mov ebx,eax ; Prepares # of loop counter cycle
是silly/unnecessary。只需执行 MOVe.
哦，还有这段代码：
jnz factoral ; Continue loop counter when ebx > 0
从来没有用过。您试图使用由初始 dec ebx 设置的零标志 (ZF)，但其他干预指令破坏了标志，因此您没有读取正确的标志值。您需要立即对 EBX 进行 比较，才能设置标志。
无论如何，在此代码的末尾，您将在 Finished 处结束，阶乘将在 EDX:EAX.
但是，这只适用于 13!。之后，它将失败。为什么？因为IMUL只用EAX作为它的被乘数，而不是EDX:EAX。 13×12×11×10×9×8×7×6×5×4×3的乘积正好在EAX，然后乘以2，乘积在EDX:EAX.但是如果你尝试做 15!，你会更早地溢出到 EDX:EAX，但是 EDX 会被后续的乘法忽略。
因此，您需要变得更聪明并编写实际执行完整 64 位乘法的代码，即，将 64 位被乘数乘以 32 位乘数以获得 64 位乘积。
幸运的是，这并不困难，尤其是，因为根据定义，阶乘仅取非负值，因此我们无需担心负数.换句话说，我们只需要做一个无符号乘法。
顺便说一下，您的 printf 格式字符串应该是 "%llu"，因为结果应该被解释为 unsigned 数量。
此代码为：
; EAX = divisor
; ECX = high bits of dividend
; EDX = low bits of dividend
imul ecx, eax ; multiply high bits of multiplicand by multiplier, quotient in ECX
mul edx ; multiply low bits of multiplicand by multiplier, quotient in EDX:EAX
add edx, ecx ; add high-order product to high bits of low-order product
; EDX:EAX = product
最后一条评论的措辞有点毛茸茸……希望代码能直观理解。我们所做的就是将乘法分成两部分，分别对 64 位值的 32 位部分进行运算，然后将结果相加。
将此乘法代码集成到您的原始代码中，我们得到如下内容：
;push ebx ; save EBX (only needed if complying with C calling convention)
mov eax, 15 ; initial value (low-order bits)
xor edx, edx ; initial value's high-order bits are 0
mov ecx, eax ; loop counter
Factorial:
dec ecx ; decrement counter
jz Finished ; when counter == 0, we're done
mov ebx, ecx ; make copy of counter
imul ebx, edx ; high-order bits * multiplier
mul ecx ; low-order bits * multiplier
add edx, ebx ; add high-order product to high-order bits of low-order product
jmp Factorial ; go back to top of loop
Finished:
;pop ebx ; restore EBX (only needed if complying with C calling convention)
...
这很有效！至少，它一直工作到 20！。在 21!，由于我们的老朋友溢出，你得到了错误的结果。 21！不适合 64 位值。
它对 0 也不起作用！—你得到的不是数学定义的结果 1，而是 0。你应该能够插入必要的比较和分支来自己解决这个问题。
有一些方法可以进一步优化这段代码，但代价是引入额外的复杂性，所以确保你首先理解这一点！
我已经提到的一个优化是确保你不做最终乘以 1。这只需要在循环体的末尾插入一个额外的比较：
;push ebx ; save EBX (only needed if complying with C calling convention)
mov eax, 15 ; initial value (low-order bits)
xor edx, edx ; initial value's high-order bits are 0
mov ecx, eax ; loop counter
Factorial:
dec ecx ; decrement counter
jz Finished ; when counter == 0, we're done
mov ebx, ecx ; make copy of counter
imul ebx, edx ; high-order bits * multiplier
mul ecx ; low-order bits * multiplier
add edx, ebx ; add high-order product to high-order bits of low-order product
cmp ecx, 1
jg Factorial ; keep looping as long as counter > 1
Finished:
;pop ebx ; restore EBX (only needed if complying with C calling convention)
...
您可以通过将初始比较提升到循环之外来稍微改进一下：
;push ebx ; save EBX (only needed if complying with C calling convention)
mov eax, 15 ; initial value (low-order bits)
xor edx, edx ; initial value's high-order bits are 0
mov ecx, eax ; loop counter
dec ecx ; decrement counter
jz Finished ; when counter == 0, we're done, so skip the loop
Factorial:
mov ebx, ecx ; make copy of counter
imul ebx, edx ; high-order bits * multiplier
mul ecx ; low-order bits * multiplier
add edx, ebx ; add high-order product to high-order bits of low-order product
dec ecx ; decrement counter
jg Factorial ; keep looping as long as counter > 1
Finished:
;pop ebx ; restore EBX (only needed if complying with C calling convention)
...
并且通过简单的优化就可以做到这一点。对于其他想法，您可以 explore what C compilers emit for similar code，但请注意，此代码的大部分内容都非常重要。 （GCC 6.3 的输出看起来很像我的代码，但 GCC 7.1 展开循环以提高速度，但导致代码更加混乱和复杂 read/understand。）除此之外，还要注意 C 编译器不必须有完美的优化器！通常情况下，专业的汇编程序员可以编写比编译器生成的代码更优化的代码（尽管他们不能那么快！）。
Extra: Would using shl eax, 1 to calculate the 2nd degree portion (n*2) for the intermediate be better than using imul for each and every degree.
没有
首先，你真的不想写 shl reg, 1 除非你真的需要设置进位标志。左移 1 相当于乘以 2，相当于将值加到自身上。所以，add reg, reg 更简单、更好、更快。
但是，在这种情况下，即使那样也不会更好。虽然简单的移位或加法确实通常比乘法快（但是 IMUL 和 SHL/ADD.
不过，事实上，我们可以对每个 2 的幂进行 shl reg, x 运算——这样会更快吗？不，出于同样的原因。实际上，更糟的是，因为它会 增加 错误预测的机会。条件会按照分支预测算法不太可能理解的模式交替出现，从而导致错误预测。