Как реализовать умножение и деление в сборке MIPS без использования встроенных инструкций?

Question

Хорошо, вот проблема. Я должен был написать программу MIPS, которая получила 2 входных номера от пользователя. Затем мне пришлось написать код, который бы выводил произведение, частное и остаток для 2 чисел, введенных пользователем.

Так вот, это было довольно просто. Тем не менее, я не осознавал, что мы не можем использовать операнды умножения и деления в программе. Теперь я не знаю, что делать, потому что я не понимаю, как это сделать без операндов умножения и деления. Я использовал его всего два раза за всю программу, он отлично работает, но мой профессор не примет это, и теперь мне грустно. Любая помощь будет оценена. Спасибо

Вот мой код

# Given positive integers a and b, output a/b and a%b.
  .data
str1: .asciiz "Enter a: "
str2: .asciiz "Enter b: "
str3: .asciiz "a/b = "
str4: .asciiz "a%b = "
str5: .asciiz "a*b = "
newline: .asciiz "\n"
  .text

main: li   $v0, 4            # system call code for print_string
  la   $a0, str1         # address of str1
  syscall                # print str1

#get the first number from user, put it into $s0

li   $v0, 5            # system call code for read_int
  syscall                # read an integer into $v0 from console
  add  $s0, $v0, $zero   # copy $v0 into $s0 (a)


#read print_string for str2
li   $v0, 4            # system call code for print_string
  la   $a0, str2         # address of str1
  syscall                # print str1

# get second number from user, put it into $t1  
li  $v0, 5      #load syscall for read_int
syscall         #make the syscall
move $s1, $v0       #move the number read into $s1(b)

#DO THE CALCULATIONS................................................
div $s0, $s1        #diving $s0 by $s1
mflo    $t0         #storing value of lo(quotient) in
                #register $t0
mfhi    $t1         #storing value of hi(remainder) in
                #register $t1

mult $s0, $s1
mflo $t2


li $v0,1
move $a0, $t2
syscall

li $v0,4
la $a0, str5
syscall

#read print_string for str3
li   $v0, 4            # system call code for print_string
  la   $a0, str3         # address of str1
  syscall                # print str1   

#print a/b
li  $v0, 1      #load syscall print_int into $v0
move $a0, $t0      #move the number to print into $t2
syscall
# read print string for str4
li $v0, 4
    la $a0, str4
    syscall
# print remainder
li $v0, 1
move $a0, $t1
syscall

#end of program
li  $v0, 10     #system call code for exit
syscall

Answer 1

То, что вы ищете, это битовое умножение / деление.

Я не уверен, что могу кратко изложить это, но здесь я приведу пример:

Умножить

Допустим, вы хотите умножить число 6 на число 5.
Если a = число 6, то (в упрощенном 8-разрядном) это:
a=00000110

Если b = число 5, то (в упрощенном 8-битном) это будет:
b=00000101

Чтобы умножить эти числа, вам нужно сместиться на ближайшую кратную двух под цифрой, затем добавить.

Например, ближайшее кратное 2 ниже 5 равно 4, то есть 2 ^ 2;
Таким образом, мы побитно сдвигаемся влево a (число 6) 2 раза:
a << 2
Который сейчас делает это 00011000

Это означает, что мы теперь умножены на 4; чтобы теперь умножить это на 5, мы просто добавляем a снова:

     00011000  
    +00000110  
    =00011110  
    =30 (base 10)

Что составляет 6 * 5.

Давайте попробуем это снова с 12 * 11 Ближайшее значение, кратное 2 ниже 11, равно 8 (2 ^ 3). Это означает, что нам нужно будет поразрядно сдвинуть число 12 3 раза, а затем добавить его к себе еще 3 раза.

    00001100 = 12
    //Let's bitshift by 3
    01100000 = 96
    //Let's add 12 3 times
    01100000
   +00001100
   =01101100 = 108
   +00001100
   =01111000 = 120
   +00001100
   =10000100 = 132 = 12*11

Разделить

Чтобы разделить 12 на 11, вы идете другим путем; вычтите 12 из 132, 3 раза, затем сдвиньте вправо 3 раза (для деления на 8)

Соответствующий ресурс (ы)

Это лучшее, что я могу сделать прямо сейчас; если вы хотите больше, с соответствующими алгоритмами на C, взгляните на http://www.programmersheaven.com/mb/CandCPP/295363/295363/bitwise-multiplication--division/

Если вы хотите, чтобы любой из этих ответов был расширен, прокомментируйте ниже;

P.S. Я показал вам два примера с простыми числами (неприятно), но что, если вы получите число, подобное 12? Логически, исходя из того, что я сказал, ближайшее кратное 2 - это 8 (2 ^ 3), поэтому вам нужно сдвинуть бит влево на 3, а затем добавить 12 к числу 4 раза.

Но если вы выполните математику, вы обнаружите, что 12 на самом деле = (2 ^ 3 + 2 ^ 2) ... что означает, что вы можете получить (12 << 3) (это 12 бит сдвига влево 3 раза ), затем добавьте его в (12 << 2) (это 12 бит сдвига влево 2 раза) ... магия! </p>

Answer 2

Попробуйте это для алгоритма умножения: это реализация алгоритма Boothe для MIPS: http://code.google.com/p/mips-booth-multiplication/source/browse/trunk/booth.asm?r=9

Answer 3

Из записи Википедии по умножению :

"Поскольку результат масштабирования по целым числам можно рассматривать как состоящий из некоторого количества копий оригинальных целочисленных произведенийзначение, большее 1, может быть вычислено путем повторного сложения "

Другими словами, для умножения a * b вы добавляете a вместе b раз.

Стратегия, которую вы упоминаете в своем комментарии (сдвиг по битам), интересна - возможно, более эффективна, но определенно НАМНОГО сложнее.

Аналогичная стратегия будет работать для деления / остатка.