Деление и по модулю целых беззнаковых чисел с 6 регистрами

Dec 02 2020

Мне нужно найти алгоритм времени журнала (для виртуальной машины), используя максимум 6 регистров (a, b, c, d, e, f), чтобы разделить два целых числа без знака N1 и N2 ([оба> = 0] положительные или 0) где, если делитель равен 0, то результат равен 0 и операции по модулю.

  • div -> N1 / N2
  • мод -> N1% N2

с такими командами, как

  • СБРОС a -> a = 0
  • ДОБАВИТЬ ab -> a = a + b
  • SUB ab -> a = max (0, ab)
  • SHR a -> a = этаж (a / 2)
  • SHL a -> a = этаж (a * 2)
  • INC a -> a + = 1
  • DEC a -> a = max (0, a-1)
  • JUMP j -> перейти на j-ю строку
  • JZERO xj -> если x равно 0, то перейти к k + j
  • JODD xj -> если x нечетное, чем перейти к k + j

Могут ли мне помочь алгоритмы?

Я могу только проверить, является ли значение в регистре ODD или ZERO.

Спасибо за помощь.

Ответы

1 PeterCordes Dec 02 2020 at 18:34

Saturating-subtract и jzeroпозволяет сравнивать «меньше или равно» (или больше), поэтому вы можете реализовать версию C ответа njuffa о том, как я могу умножать и делить, используя только битовый сдвиг и сложение? что дает частное и остаток. Поскольку у вас есть ненасыщающее добавление, вы можете реализовать добавление обертывания (а затем выполнить обнаружение выполнения вручную, проверив перенос, как Натан делает это в C.)

joddпозволяет вам проверить младший бит, например if (x&1), что позволит вам также реализовать стандартный алгоритм умножения. Итак, если у вас есть алгоритм деления, который дает вам только частное, вы можете remainder = dividend - quotient*divisorиспользовать логарифмическое умножение.


Другое двоичное деление, вопросы и ответы:

  • Как я могу умножать и делить, используя только битовый сдвиг и сложение? -другой ответ на те же вопросы и ответы, на этот раз с использованием сдвигов, чтобы «выровнять» самый значащий бит делителя с делимым, прежде чем переходить к полному делению в учебнике. Но не ясно, безопасно ли это без целых чисел расширенной ширины.
  • Целочисленное деление по логарифмическому времени с использованием только сложения и вычитания битового сдвига
  • Как я могу использовать битовый сдвиг для замены целочисленного деления?
  • Разделить на 10 с помощью битового сдвига? выполняет умножение на каждом шаге, что хорошо только в том случае, если у вас есть быстрое умножение, или для известных констант с несколькими установленными битами, поэтому требуется всего пара сдвиг / сложение. Другое преимущество - не требуется сдвиг вправо, но сдвиг вправо есть. (В отличие от некоторых игрушечных ISA)