计算绝对差| A-B |仅使用INC，DEC，JNZ，HALT进行组装-面试问题 [英] Calculate absolute difference |A-B| in assembly using only INC, DEC, JNZ, HALT - interview question

问题描述

这是我在采访中遇到的一个问题，但没有找到解决方案-因此我尝试自己解决.
我们可以在这里使用伪代码-不需要是正式代码.

This is a question I encountered in an interview and for which I didn't find a solution - so I tried to solve it myself.
We can use pseudocode here - it doesn't need to be a formal code.

问题是要获得无符号输入的绝对差:

The question is to get the absolute difference of unsigned inputs:

假设您的汇编语言仅包含以下说明: inc ， dec ， jnz 和 halt (停止 =停止运行).

Assume your assembly language includes ONLY the following instructions: inc, dec, jnz and halt (halt = stop running).

任务: A 和 B 是保存非负值的寄存器.程序应计算 | A-B | 的值，并将结果定位在 C 中.此外，该语言还包含寄存器 C ， D ，...， Z ，您可以假定它们在程序启动时初始化为零.

Task: A and B are registers that hold non-negative values. The program should calculate the value of |A-B| and locate the result in C. In addition, the language holds registers C, D, ..., Z, which you can assume are initialized to zero at program start.

这是我的尝试，我的主要思想是将两个寄存器的值都减小到一个变为零，然后将另一个寄存器的值移动到 C :

This is my attempt, where my main idea is to decrease both registers till one becomes zero, and then move the other register's value to C:

// zero case handling
dec a
inc a
jnz a_pre_loop_not_zero // a != 0
// a == 0, check if b == 0
dec b
inc b
jnz move_b_to_c // a == 0, b !=0 
// a == 0 , b == 0 -> c needs to be 0
halt  

a_pre_loop_not_zero:
  dec b
  inc b
  jnz main_loop // a != 0, b != 0

// a != 0 , b == 0
move_a_to_c:
    inc c
    dec a
    jnz move_a_to_c
    halt  

// a,b != 0
main_loop:
  dec b
  jnz b_not_zero // b!=0
  // b became zero before a -> a contains result+1 now
  dec a
  jnz move_a_to_c
  halt // if a == 0 now -> a == b -> c needs to be 0

  b_not_zero:
      dec a
      jnz main_loop // a != 0

  // a became zero before b -> b contains the result now
  move_b_to_c:
    inc c
    dec b
    jnz move_b_to_c
    halt              

现在，我认为它可以工作-但看起来很脏.
更具体地说，我认为零情况处理可以以一种更简洁的方式完成，也许我们甚至可以在主循环中考虑(无需在预循环代码中进行检查).
另外，我没有使用寄存器 C ， D ，...， Z 可以被初始化为0的事实-这让我怀疑也许还有更好的方法.

Now, I think that it works - but it looks very dirty.
To be more specific, I think the zero case handling can be done in a cleaner way, and maybe we can even consider it in the main loop (without checking it in a pre loop code).
Also, I didn't use the fact that registers C, D, ..., Z are initialized to 0 and can be used - which makes me suspect that maybe there's a better way.

有没有更好的解决方案来解决这个问题?

Is there a better solution for this problem?

推荐答案

现在，我认为它可以工作-但看起来很脏.

Now, I think that it works - but it looks very dirty.

您可以通过编写更多的组装方式

You can improve how it looks by writting it more the assembly way:

    dec A                   // zero case handling
    inc A
    jnz A_pre_loop_not_zero // A != 0
    dec B                   // A == 0, check if B == 0
    inc B
    jnz move_B_to_C         // A == 0, B !=0 
    halt                    // A == 0, B == 0 -> C needs to be 0
A_pre_loop_not_zero:
    dec B
    inc B
    jnz main_loop           // A != 0, B != 0

move_A_to_C:                // A != 0, B == 0
    inc C
    dec A
    jnz move_A_to_C
    halt  
main_loop:                  // A,B != 0
    dec B
    jnz B_not_zero          // B != 0
    dec A                   // B became zero before A -> A contains result+1 now
    jnz move_A_to_C
    halt                    // if A == 0 now -> A == B -> C needs to be 0
B_not_zero:
    dec A
    jnz main_loop           // a != 0
move_B_to_C:                // a became zero before b -> b contains the result now
    inc c
    dec B
    jnz move_B_to_C
    halt              

建议Eric Eidt 先将 A 和 B 递增，然后远离可能的零.
我认为我们可以假设 inc 和 dec 都使用环绕逻辑.如果不是，这些 A 和 B 上的增量将是错误的！

The suggestion by Eric Eidt to increment A and B beforehand moves away from possible zeroes.
I think we can assume that both inc and dec use wraparound logic. If not these increments on A and B would be wrong!

    inc     A
    inc     B

L1: dec     A
    jnz     L4

L2: dec     B
    jnz     L3
    halt
L3: inc     C      ; A == 0 -> C = B
    jnz     L2     ; (*)

L4: dec     B
    jnz     L1

L5: inc     C      ; B == 0 -> C = A
    dec     A
    jnz     L5
    halt

递增 C 寄存器将永远不会产生零.因此，标有星号的条件跳转将始终跳转.这省去了2条指令.

Incrementing the C register will never produce zero. Therefore the conditional jump marked with an asterisk will always jump. This shaved off 2 instructions.

也许有点老派，但是绝对好看...

A bit old school perhaps, but definitively nice to look at...

这篇关于计算绝对差| A-B |仅使用INC，DEC，JNZ，HALT进行组装-面试问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！