Вычислить абсолютную разницу | A-B | в сборке с использованием только INC, DEC, JNZ, HALT - вопрос собеседования

Это вопрос, с которым я столкнулся во время интервью и для которого я не нашел решения, поэтому я попытался решить его сам.
Мы можем использовать здесь псевдокод - это не обязательно должен быть формальный код.

Вопрос в том, чтобы получить абсолютную разницу беззнаковых входов:

Предположим, ваш язык ассемблера включает ТОЛЬКО следующие инструкции: inc, dec, jnz и halt (halt = остановить выполнение).

Задача: A и B - это регистры, в которых хранятся неотрицательные значения. Программа должна вычислить значение |A-B| и найти результат в C. Кроме того, язык содержит регистры C, D, ..., Z, которые, как вы можете предположить, обнуляются при запуске программы.

Это моя попытка, где моя основная идея - уменьшить оба регистра до тех пор, пока один из них не станет равным нулю, а затем переместить значение другого регистра на 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 и могут быть использованы - что заставляет меня подозревать, что, возможно, есть лучший способ .

Есть ли лучшее решение этой проблемы?


algorithm assembly pseudocode
person Rodrigo    schedule 31.05.2020    source источник
comment
Ваш подход кажется здравым. Я мог бы подумать о том, чтобы пропустить обработку нуля, увеличив их оба, чтобы начать, а затем перейти непосредственно к основному циклу.   -  person Erik Eidt    schedule 31.05.2020
comment
@ErikEidt: это было бы легко, если бы у нас тоже был JZ; do { if(--a == 0) break; } while(--b); Но мы можем синтезировать JZ из JNZ по фиктивному INC / JNZ регистра, который был равен нулю в начале цикла. Или inc / dec / jnz ненулевого регистра.   -  person Peter Cordes    schedule 01.06.2020
comment
Я голосую за закрытие этого вопроса, потому что это кодовый гольф, а не практическая проблема программирования.   -  person Ross Ridge    schedule 01.06.2020

Ответы (1)


arrow_upward
1
arrow_downward

Я думаю, что это работает, но выглядит очень грязно.

Вы можете улучшить его внешний вид, написав более способом сборки:

    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

Предложение Эрика Эйдта для увеличения A и B заблаговременно удаляет возможные нули.
Я думаю, мы можем предположить, что и inc, и dec используют циклическую логику. Если бы не эти приращения на A и B, было бы неправильно!

    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 инструкции.

Возможно, немного старой школы, но определенно приятно смотреть ...

person Sep Roland    schedule 01.06.2020