7

あるインタビューで、「新しい」プリミティブ アセンブリについて非常に複雑な質問を受けました (QA が Python に基づく QA のテストについて教えてくれたのに、なぜアセンブリの知識が必要なのですか?)、それは次のようになります。 :

アセンブリ言語に次の命令のみが含まれていると仮定します。

  • 'inc REG': 指定されたレジスタを 1 つインクリメントします。
  • 'dec REG': 指定されたレジスタを 1 減らします。
  • 'jnz LABEL': 前の命令の結果がゼロでない場合、指定された LABEL にジャンプします。
  • 'HELT': 実行を停止します。

タスク: A および B レジスタは負でない値を保持します。プログラムは A*B の値を計算し、結果を C に配置する必要があります。さらに、言語はレジスタ C、D、...、Z を保持します。これらは、プログラムの開始時にゼロに初期化されると想定できます。

ここには、より注意が必要なポイントがいくつかあります。たとえば、A および\または B の値がゼロになる可能性があることを事前に理解しておく必要があります..ゼロによる倍数は...ゼロです..これは非常に難しいです..

PSその質問のために、「my_atoi()」の質問の実装に到達することはできませんでした.. :-(

ありがとう ！

4

4 に答える 4

5

完全な答えを出すつもりはありませんが、ここで重要なのは、movルーチンを自分で定義する必要があるということです。dec Xwhere hold 0 が負の (または非常に大きな) 数値を生成すると仮定すると、X次のように実行できます。

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 に変換する必要があります。幸いなことに、ゼロであることがわかっている変数がたくさんあるので、そのうちの 1 つがゼロかどうかをテストできます。

    # 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 に答える
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 に答える