Assembler. деление

[kventin_zhuk]

Здравствуйте. Преподаватель поставил задачу разделить число на само себя(12h/12h в моём варианте). Нельзя использовать команду DIV, а можно только команду сдвига SRH, команду and для проверки чётности и команду sub. Уже неделю ломаю мозг, всё никак. Из того,что придумал:

mov ax,12h
shr ax,1 12h/2=9
shr ax,1; 9h/2=4 -----> CF=1
shr ax,1 4/2=2
shr ax,1 2/2=1

Четырьмя последовательными сдвигами я достиг результата 1. Число 2 в 4-ой степени = 10h. Преподаватель говорит, что я разделил 12h/10h , а мне нужно 12 на 12. т.е (2^4+2);
Помогите плз, кто знает чем.

[vadimych]

Преподаватель поставил задачу разделить число на само себя(12h/12h в моём варианте)

А что, может быть результат не равный единице?

[f.hump]

вопрос не в результате, а в упражнении.

не знаю зачем свиг и "и". все что приходит на ум, это вычитать 12h пока вычитается и инкрементить счетчик вычитаний.

[kventin_zhuk]

Сообщение от f.hump

вопрос не в результате, а в упражнении.

не знаю зачем свиг и "и". все что приходит на ум, это вычитать 12h пока вычитается и инкрементить счетчик вычитаний.

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

mov bp,300
mov ax,718b
mov [bp],ax
mov ax,[bp]
mov bx,59
mov [bp+10],bx;
and ax,1
jnz 129
and bx,1
jnz 129
mov ax,718b
mov bx,59
shr ax,1
shr bx,1
jmp 12F
mov ax,718b
mov bx,59
inc cx
sub ax,bx
jge 12F
add ax,bx
dec cx

[DiemonStar]

и какой результат хочет увидеть ваш преподаватель? целое число с остатком или дробное число?

[Mikl___]

kventin_zhuk
ниже несколько способов деления без использования команд div/idiv

Табличное преобразование
Для реализации деления на заранее известное число можно использовать табличное преобразование (команда XLAT).

Деление через вычитание
Частное от деления можно представить как количество вычитаний делителя из делимого до тех пор, пока делимое сохраняет знак. Это дало возможность организовать деление путем повторения последовательности вычитаний с проверкой знака делимого. Если произошла перемена знака, то нужно уменьшить счетчик числа вычитаний на единицу, а делимое и делитель сложить. Теперь делимое будет равно остатку, а счетчик числа вычитаний равен частному. Так делили на ранних микропроцессорах Intel (i4004, i8080), которые еще не поддерживали команду деления.

Деление через вычитание, сложение и сдвиги
При делении двоичных чисел используют два алгоритма: алгоритм деления без восстановления и алгоритм деления с восстановлением. При делении с помощью вычитаний, сложений и сдвигов можно использовать две схемы.
Схема а – делимое по мере вычисления сдвигается влево, делитель остается неподвижным.
Схема б – делимое неподвижно, а делитель по мере вычисления сдвигается вправо. Цифры частного формируются по значению бита переноса CF, устанавливаемого при вычитании или сложении делителя и делимого, и сдвигаются влево.
Таким образом, можно использовать четыре способа деления через вычитания, сложения и сдвиги.
Показываю алгоритм деления без восстановления на примере 125/11=11 остаток 4. Из делимого вычитается делитель, умноженный на степень двойки. Произведение числа на 2^n эквивалентно сдвигу этого числа на n разрядов влево. Если знак результата положительный, то нужно прибавить 2^n к частному, если знак результата отрицательный – частное не увеличивается. Когда знак результата меняется на отрицательный, вычитание заменяется сложением. Так повторяется при уменьшающихся степенях двойки до тех пор, пока не будет достигнута степень, равная нулю. Остатком считается последний положительный результат.
Делим 125 на 11. Делитель укладывается в байт (11<255), поэтому начинаем с 2^7. В начале вычисления частное всегда равно 0:
125 – 11 × 2^7= –1283
–1283 +11 × 2^6= –579
–579 +11 × 2^5= –227
–227 +11 × 2^4= –51
–51 + 11 × 2^3= 37 результат положительный, поэтому складываем 2^3 с частным, частное равно 8+0=8
37 – 11 × 2^2= – 7
–7 + 11 × 2^1= 15 результат положительный, поэтому складываем 2^1 с частным, частное равно 8+2=10
15 –11 × 2^0 = 4 результат положительный, поэтому складываем 2^0 с частным, частное равно 10+1=11, остаток равен 4

mov edx,ДЕЛИМОЕ
bsr ecx,edx
mov ebx,ДЕЛИТЕЛЬ
bsr eax,ebx ; чтобы не делать лишних операций
sub ecx,eax ; определим разрядность делимого и
mov ebp,1 ; делителя
shl ebp,cl
shl ebx,cl
xor eax,eax; в EAX место под частное, в EDX – остаток
or esi,-1 
a1: mov edi,ebx
add edi,esi
xor edi,esi; neg edi
add edx,edi; если esi=-1 тогда edx:=edx-ebx иначе edx:=edx+ebx
sbb esi,esi; если CF=1 тогда esi:=-1 иначе esi:=0
mov edi,esi
and edi,ebp; если esi=-1 тогда edi:=ebp иначе edi:=0
add eax,edi; если esi=-1 тогда eax:= eax + ebp
test edx,edx
jz a2;exit
shr ebx,1
shr ebp,1
jnz a1
a2:

Деление чисел при помощи вычитаний, сложений и сдвигов в ряде случаев оказывается быстрее, чем использование команд DIV или IDIV. Кроме того, деление при помощи вычитаний, сложений и сдвигов не так очевидно для «кодокопателя», чем команды DIV или IDIV.

[Indian]

18 = 10010 = 2^4 + 2^1
A*18 = A*(2^4 + 2^1) = A*2^4 + A*2^1
A/18 = A*(1/18)
1/18 = 2^(-5) + 2^(-6) + 2^(-7) (о представлении дробных чисел в двоичной системе см. вики)
A*(1/18) = A*2^(-5) + A*2^(-6) + A*2^(-7)
A*(1/18) = 0 - A*2^(-5) - A*2^(-6) - A*2^(-7)
Только это работает как-то неправильно: 18/18 даст 0(т.к. 18>>5 = 0, 18>>6 = 0, 18>>7 = 0.)

[kventin_zhuk]

Всем спасибо, разобрался)

[Mikl___]

Indian
A*(1/18)~A*2^(-4)-A*2^(-7)+A*2^(-10)=A/17,964912280701754385964912280702
при А=18 даст 1