Как исправить этот код, чтобы выполнить «Деление с использованием вычитания» - PullRequest
Новая
       63

Как исправить этот код, чтобы выполнить «Деление с использованием вычитания»

1 голос
/ 01 мая 2019

Моя программа должна выполнять деление с использованием вычитания. Тем не менее, я получаю бессмысленные результаты в качестве вывода. Может ли кто-нибудь помочь мне с моей процедурой и циклом внутри? Спасибо. 

div proc
pushad

mov ecx,firstInt
mov ebx,0
subtracting:
    sub ebx,secondInt
loop subtracting
mov divResult,ebx
popad
ret
divt endp

1 Ответ

2 голосов
/ 02 мая 2019

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

    mov     ecx, firstInt
    mov     ebx, -1
subtracting:
    inc     ebx
    sub     ecx, secondInt
    jnb     subtracting
    mov     divResult, ebx

EDIT

В приведенном выше коде по-прежнему не хватает проверки нулевого делителя. Если мы допустим делитель нуля, код будет работать вечно, потому что вычитание нуля никогда не приведет к заимствованию!

Это простое решение выполняет свою работу, но оно неприемлемо медленно для больших факторов. Это требует лучшего решения, не выдавая, конечно, задание «Деление с использованием вычитания» или «Не использовать div (или любую аналогичную инструкцию)».

Чтобы имитировать инструкцию div: 

divide:
    mov     eax, firstInt
    xor     edx, edx
    div     secondInt       ; -> EDX is remainder, EAX is quotient

мы можем написать: 

simple:
    mov     edx, firstInt
    mov     eax, -1
.A: inc     eax
    sub     edx, secondInt
    jnb     .A
    add     edx, secondInt  ; -> EDX is remainder, EAX is quotient

Проблема с этим простым решением состоит в том, что мы могли бы вычитать небольшое число много-много раз. Что если бы мы могли найти способ вычесть больше сразу?
Мы можем, если вычтем двоичные кратные делителя (* 1, * 2, * 4, * 8, * 16, ...). Это будет суммирование этих факторов, которые производят частное.

Для расчета, например 503 / 20 мы бы вычли следующее: 

503 - (20 * 16) = 183
183 - (20 *  8) =  23
 23 - (20 *  1) =   3 <-- is remainder
            --
            25 <-- is quotient

В коде: 

complex:
    mov     edx, firstInt
    xor     eax, eax
    jmp     .C
.A: rol     ecx, 1
    shl     ebx, 1
    jc      .B
    cmp     ebx, edx
    jbe     .A
.B: rcr     ebx, 1
    add     eax, ecx
    sub     edx, ebx
.C: mov     ebx, secondInt
    mov     ecx, 80000000h
    cmp     edx, ebx
    jnb     .A
; -> EDX is remainder, EAX is quotient

Чтобы проиллюстрировать важность разработки лучшего решения, я выделил несколько разделов: 

                       simple      complex    divide
                   --------------  --------  --------
4294967295 /   1   8087730.0 µsec  3.0 µsec  0.3 µsec
2147483648 /  10    405994.0 µsec  1.3 µsec  0.1 µsec
     47623 / 320         0.4 µsec  0.2 µsec  0.1 µsec
  • 4294967295 / 1 является наихудшим делением
  • 2147483648 / 10 используется для начала отображения номера 2147483648
  • 47623 / 320 используется для преобразования адреса смещения 2566-цветного видеосигнала 320x200 47623 в (x, y) координаты
...