assembly 如何求一个数的因数?

34gzjxbg  于 2023-03-23  发布在  其他
关注(0)|答案(1)|浏览(141)

给定一个非负整数n,从[2,n-1]范围内找出这个数的约数。
input:一个不超过1000的非负数整数n。
输出:整数非负数
我试了一下代码,但我不能总是得到正确的结果。

%include"io.inc"
section .text
global CMAIN
CMAIN:
    ;write your code here
    GET_UDEC 4, eax
    mov ebx, 2
    mov ecx, 0
 cycle:
    cmp eax, ebx
    jbe end;
    xor edx, edx
    div ebx
    mul eax, ebx
    inc ebx
    cmp edx, 0
    jne cycle;
    inc ecx;
    jmp cycle;
 end:
    PRINT_UDEC 4, ecx
    NEWLINE
    
    xor eax, eax
    ret

我的代码有问题吗?请给我指出来。

a9wyjsp7

a9wyjsp71#

我不能总是得到正确的结果。
原因是,在循环的每次迭代中,你改变了被除数,而被除数应该保持不变。我看到你添加了一条mul eax, ebx指令,试图将被除数恢复到原始值,但遗憾的是,如果存在来自除法的余数,则该指令本身不能重新创建被除数。可以使用的是imul eax, ebx后跟add eax, edx(1),但首选的解决方案是在每次除法之前重新加载被除数。要么使用push eaxpop eax(2),要么从用输入的数字初始化的备用寄存器加载EAX(3)。

  • 溶液1
GET_UDEC 4, eax
   mov  ebx, 2
   mov  ecx, 0
  cycle:
   cmp  eax, ebx
   jbe  end
   xor  edx, edx
   div  ebx
   IMUL EAX, EBX    <<<< Does not destroy the remainder in EDX
   ADD  EAX, EDX    <<<<
   inc  ebx
   cmp  edx, 0
   jne  cycle
   inc  ecx
   jmp  cycle
  end:
  • 解决方案二
GET_UDEC 4, eax
   mov  ebx, 2
   mov  ecx, 0
  cycle:
   cmp  eax, ebx
   jbe  end
   xor  edx, edx
   PUSH EAX         <<<<
   div  ebx
   POP  EAX         <<<<
   inc  ebx
   cmp  edx, 0
   jne  cycle
   inc  ecx
   jmp  cycle
  end:
  • 解决方案三
GET_UDEC 4, eax
   MOV  ESI, EAX    <<<<
   mov  ebx, 2
   mov  ecx, 0
  cycle:
   cmp  eax, ebx
   jbe  end
   xor  edx, edx
   div  ebx
   MOV  EAX, ESI    <<<<
   inc  ebx
   cmp  edx, 0
   jne  cycle
   inc  ecx
   jmp  cycle
  end:

可以更早停止循环

输入是不超过1000的非负数N。
在[2,N-1]范围内找出这个数的约数。
考虑N=1000。您现在的代码将1000除以[2,999]范围内的每个数字。总共998次除法!现在看看当您开始将1000除以[501,999]范围内的数字时会发生什么:余数永远不会为零,因此代码将永远不会再增加ECX。简而言之,您可以在EBX超过N/2时停止循环。

GET_UDEC 4, eax
     MOV  EDI, EAX    <<<<
     SHR  EDI, 1      <<<< EDI is now N/2
     MOV  ESI, EAX    <<<<
     XOR  ECX, ECX    <<<<
     mov  ebx, 2
    cycle:
     CMP  EBX, EDI    <<<< Exits on EBX > N/2, and also exits on N < 4
     JA   end         <<<<
     xor  edx, edx
     div  ebx
     MOV  EAX, ESI    <<<<
     inc  ebx
     TEST EDX, EDX    <<<<
     JNZ  cycle       <<<<
     inc  ecx
     jmp  cycle
    end:

相关问题