14

Пусть A и B – два 8-разрядных регистра в обыкновенном 16-разрядном процессоре. Следующая процедура выполняет сдвиг регистра A на число разрядов, заданное в регистре B. 

Loop:
  SHR A  ;shift right A
  DEC B  ;decrement B
  JNZ Loop  ;loop again

Задача - Написать программу, которая выполняет сдвиг быстрее. Пользоваться многократным сдвигом запрещено.

ЗЫ Эту задачу когда-то мне предложили на собеседовании. Я ее решил не верно. У кого какие мысли? Гугл не поможет :) Надо думать самому!

UPD: Нашел свое неверное решение

 MOV AH,A
 MOV AL,B
Label:  
 SHR AH
 DEC AL
 JNE Label
LEQADA
  • 5,185
Nicolas Chabanovsky
  • 51,426
  • 87
  • 267
  • 507
  • ничего себе у вас процессор, в котором можно оперировать 4 разрядными словами :-) – psyhitus Jan 18 '11 at 14:09

6 Answers6

16

И третий вариант:) Предложен моим коллегой. Развернуть цикл. 

jmp $+sizeof(shr a)*(8-b) // $ - это адрес следующей за jmp инструкции
shr a
shr a
shr a
shr a
shr a
shr a
shr a
shr a
a_s
  • 2,329
  • 14
  • 14
6

Начнем с того, что приведенный выше код не позволяет выполнить сдвиг на 0(ноль) разрядов, т.е. он всегда выполняет хотябы один сдвиг. (Жутко ненавижу задачи про ассемблерную оптимизацию)).

Да, первое, что приходит на ум это вопрос: о каком "обыкновенном" процессоре речь? Если это RISC, то можно оперется на delay slot при бранчевании и написать так:

loop:
dec B
jnz loop
shr A

Т.е., здесь "shr A" выполнится в delay slot предыдущей инструкции бранчевания "jnz loop", что позволит нам сэкономить 'B' операций. Для RISC процессоров этот и приведенный выше коды эквивалентны.

Да, на этом моя мысль заканчивается))

a_s
  • 2,329
  • 14
  • 14
  • 2
    Поправьте, если я не то говорю :). Получается что команда shr A все равно выполниться B раз? – Nicolas Chabanovsky Jan 18 '11 at 08:38
  • Присоединяюсь. – Nicolas Chabanovsky Jan 18 '11 at 09:51
  • 2
    Да, точно, она выполняется в то же время, когда выполняется jnz(точнее в delay slot этой команды, т.е. пока процессор пытается загрузить в конвейер команду на которую должен быть сделан переход, мы можем либо ничего не делать(просто пропустить такт, а можем выполнить какую-нибудь простую команду типа сдвига) http://en.wikipedia.org/wiki/Delay_slot – a_s Jan 18 '11 at 10:32
  • Да, я читал вики. Крутая тема, сразу не дорубил :) ! – Nicolas Chabanovsky Jan 18 '11 at 13:32
5

С помощью AND убираем бесполезные сдвиги. немного увеличив время выполнения кода на 2 лишних такта, получили существенное увеличение производительности.

    and B, 7
    jz fin
loop: 
    shr A
    dec B
    jnz loop
fin:
psyhitus
  • 3,667
  • 2
  • 20
  • 29
  • Не могли бы по подробнее объяснить, в чем ускорение? Зачем нужна первая строка? Она же ничего не делает (7 - это 8 по 1, при выполнении команды and над числом и данной маской не изменит число)? А остальной цикл эквивалентен данному в задаче? – Nicolas Chabanovsky Jan 18 '11 at 08:33
  • Да цикл эквивалентен, если не считать того, что это не цикл). Видимо в конце имелось ввиду jnz loop. – a_s Jan 18 '11 at 10:33
  • команда and B,7 в IA-32 накладывает маску на переменную B и сохраняет в неё же результат. Нет смысл делать больше 7 сдвигов, так как число обнулится при B > 7. – psyhitus Jan 18 '11 at 14:07
4
mov cl,b
shr a,cl
psyhitus
  • 3,667
  • 2
  • 20
  • 29
Larionov
  • 41
  • 1
  • 1
    Вы невнимательно прочитали вопрос, пользоваться многократным сдвигом нельзя! – Nicolas Chabanovsky Jan 18 '11 at 08:27
4

Есть еще идейка, возможно это хотели увидеть ваши экзаменаторы).

mov dx, a
mov bx, b //кол-во сдвигов до правого края DL
mov ax, 8
sub ax, bx //кол-во сдвигов до правого края DH
cmp ax, bx
jbe loop_shl: // если ax <= bx двигаем влево на ax, берем результат из DH
loop_shr: // иначе двигаем вправо на bx, берем результат из DL
shr dx
dec bx
jnz loop_shr
jmp end:

loop_shl:
shl dx
dec ax
jnz loop_shl


end:
a_s
  • 2,329
  • 14
  • 14
  • не-не-не, это слишком громоздко :-) – psyhitus Jan 18 '11 at 14:03
  • В задание сказано, что A и B регистры, самые быстрые операции с регистрами, зачем засовывать их в другие регистры?) – psyhitus Jan 18 '11 at 14:10
  • @psyhitus - для понятности, где что лежит, сколько разрядов занимает. Регистров A и B в x86 ассемблере не встречал. – a_s Jan 18 '11 at 21:09
4

Можно сделать следующим образом:

; прошу прощения за ошибки, давно не писал..

data segment
       ; 0 1 2 3  4  5  6   7   8
array db 1,2,4,8,16,32,64,128,256
data ends

code segment
...
start:
...
mov cx,[bx+array]
mul cx
...
code ends
end start

суть идеи: при умножении или делении числа на два, его двоичный код смещается влево или вправо соответственно, это я и попытался использовать. В массиве мы храним числа, на которые мы должны умножить исходное число(значение ax), число сдвигов(значение bx) используется как смещение в массиве.

Roman Kovtuh
  • 141
  • 5