7

在我的一次采访中,我在“新”原始程序集中遇到了一个非常复杂的问题(当他们告诉我他们基于 Python 的 QA 测试时,为什么 QA 需要汇编知识......?),它是这样的:

假设您的汇编语言仅包含以下说明:

  • 'inc REG': 将给定的寄存器加一。
  • 'dec REG':将给定寄存器减一。
  • 'jnz LABEL': 如果前一条指令的结果不为零,则跳转到给定的 LABEL。
  • 'HELT': 停止运行。

任务:A 和 B 寄存器保存非负值。程序应该计算 A*B 的值并将结果定位在 C 中。此外,该语言保存寄存器 C、D、...、Z,您可以假设它们在程序开始时被初始化为零。

这里有几点需要更多注意,例如您必须提前考虑 A 和\或 B 值可能为零..和零的倍数是...零..这太难了..

PS由于那个问题,我没有实现'my_atoi()'的问题.. :-(

谢谢 !

4

4 回答 4

5

我不会给出完整的答案,但这里的关键是你必须自己定义一个mov例程。假设dec XwhereX保持 0 产生一个负数(或非常大),可以这样完成:

MOV_AD:     ; copy value in A to D, using E as scratch space
    inc A   ; must be non-zero for jnz to work below
COPYLOOP:
    inc D
    inc E
    dec A
    jnz COPYLOOP
    dec D   ; undo the first inc A in D

            ; E now contains the initial value of A + 1
MOVBACK:    ; move value in E back to A
    inc A
    dec E
    jnz MOVBACK
    dec A   ; undo the first inc A

WIPE_E:     ; wipe the scratch space
    dec E
    jnz WIPE_E

一旦有了适当的mov例程,就可以将加法实现为重复递增,将乘法实现为重复加法。在这两种情况下,您都需要inc技巧才能开始jnz工作,而在乘法例程中,您需要以减法结束。

于 2012-10-14T11:06:57.260 回答
4

逐步分解:

原来的:

C = A * B

相当于:

C = 0
while A != 0:
   dec A
   C += B

相当于:

C = 0
while A != 0:
   dec A
   # Note: Following block of code changes B but sets it back to
   #       original value when done
   Z = 0
   while B != 0:
       dec B
       inc Z
       inc C
   B = Z

相当于:

C = 0
Z = 0
while A != 0:
   dec A
   # Note: Following block of code changes B but sets it back to
   #       original value when done
   while B != 0:
       dec B
       inc Z
       inc C
   while Z != 0:
       dec Z
       inc B

现在我们只需要弄清楚如何翻译这个结构:

while LOOP_VAR != 0:
    dec LOOP_VAR
    ... some code here which does not use LOOP_VAR ...

这可以翻译成:

    # Next 4 lines do "if LOOP_VAR == 0: goto loop_end"
    inc LOOP_VAR
    dec LOOP_VAR  # To set flags
    jnz loop_again
    goto loop_end
loop_again:
    ... some code here which does not use LOOP_VAR ...
    dec LOOP_VAR
    jnz loop_again
loop_end:

当然,我们需要将无条件的 goto 转换为有条件的 goto。幸运的是,我们有很多已知为零的变量,因此我们可以测试其中一个是否为零:

    # Unconditional jump to "loop_end".  Note that Q is always zero.
    inc Q
    dec Q
    jnz loop_end

所以,把所有这些放在一起:

    # Next 3 lines do "if A != 0: goto outer_loop_again"
    inc A
    dec A  # To set flags
    jnz outer_loop_again

    # Unconditional jump to "outer_loop_end".  Note that Q is always zero.
    inc Q
    dec Q
    jnz outer_loop_end

outer_loop_again:

    # Next 3 lines do "if B != 0: goto addition_loop_again"
    inc B
    dec B  # To set flags
    jnz addition_loop_again

    # Unconditional jump to "addition_loop_end".  Note that Q is always zero.
    inc Q
    dec Q
    jnz addition_loop_end

addition_loop_again:
    inc Z
    inc C
    dec B
    jnz addition_loop_again
addition_loop_end:

    # Next 3 lines do "if Z != 0: goto move_loop_again"
    inc Z
    dec Z  # To set flags
    jnz move_loop_again

    # Unconditional jump to "move_loop_end".  Note that Q is always zero.
    inc Q
    dec Q
    jnz move_loop_end

move_loop_again:
    inc B
    dec Z
    jnz move_loop_again
move_loop_end:

    dec A
    jnz outer_loop_again
outer_loop_end:

    # Finished!
    helt

编辑添加:实际上,有一个稍微简单的方法。我们可以在开始时检查 A 或 B 是否为零,这将其简化为:

    # Check if A is zero, and halt if so
    # (So that multiplying by zero gives zero)
    inc A
    dec A  # To set flags
    jnz a_non_zero
    helt  # Multiplying by zero gives zero
a_non_zero:

    # Check if B is zero, and halt if so
    # (So that multiplying by zero gives zero)
    inc B
    dec B  # To set flags
    jnz b_non_zero
    helt  # Multiplying by zero gives zero
b_non_zero:

outer_loop_again:

addition_loop_again:
    inc Z
    inc C
    dec B
    jnz addition_loop_again

move_loop_again:
    inc B
    dec Z
    jnz move_loop_again

    dec A
    jnz outer_loop_again

    # Finished!
    helt
于 2012-10-14T11:09:15.753 回答
2

JNZ指令可以看作do .. while结构,@user9876代码示例:

@_loop1:        ;   do {
                ;       do {
    INC Z       ;           z++;
    INC C       ;           c++;
    DEC B       ;           b--;
    JNZ _loop1  ;       } while (b != 0);
                ;       
@_loop2:        ;       do {
    INC B       ;           b++;
    DEC Z       ;           z--;
    JNZ _loop2  ;       while (z != 0);
                ;       
    DEC A       ;       a--;
    JNZ _loop1  ;   } while (a != 0);
于 2014-08-05T02:56:06.623 回答
0

我刚刚在JJ面试时有这个任务。这似乎是一个正确的解决方案。如我错了请纠正我

INC A
DEC A
JNZ L0
HELT

L0:
INC B
DEC B
JNZ L1
HELT

L1:
INC C
INC D
DEC A
JNZ L1
DEC B
JNZ L2
HELT

L2:
INC C
INC A
DEC D
JNZ L2
DEC B
JNZ L1
HELT
于 2018-07-30T17:52:43.847 回答