Деление и по модулю целых беззнаковых чисел с 6 регистрами
Мне нужно найти алгоритм времени журнала (для виртуальной машины), используя максимум 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.
Спасибо за помощь.
Ответы
Saturating-subtract и jzero
позволяет сравнивать «меньше или равно» (или больше), поэтому вы можете реализовать версию C ответа njuffa о том, как я могу умножать и делить, используя только битовый сдвиг и сложение? что дает частное и остаток. Поскольку у вас есть ненасыщающее добавление, вы можете реализовать добавление обертывания (а затем выполнить обнаружение выполнения вручную, проверив перенос, как Натан делает это в C.)
jodd
позволяет вам проверить младший бит, например if (x&1)
, что позволит вам также реализовать стандартный алгоритм умножения. Итак, если у вас есть алгоритм деления, который дает вам только частное, вы можете remainder = dividend - quotient*divisor
использовать логарифмическое умножение.
Другое двоичное деление, вопросы и ответы:
- Как я могу умножать и делить, используя только битовый сдвиг и сложение? -другой ответ на те же вопросы и ответы, на этот раз с использованием сдвигов, чтобы «выровнять» самый значащий бит делителя с делимым, прежде чем переходить к полному делению в учебнике. Но не ясно, безопасно ли это без целых чисел расширенной ширины.
- Целочисленное деление по логарифмическому времени с использованием только сложения и вычитания битового сдвига
- Как я могу использовать битовый сдвиг для замены целочисленного деления?
- Разделить на 10 с помощью битового сдвига? выполняет умножение на каждом шаге, что хорошо только в том случае, если у вас есть быстрое умножение, или для известных констант с несколькими установленными битами, поэтому требуется всего пара сдвиг / сложение. Другое преимущество - не требуется сдвиг вправо, но сдвиг вправо есть. (В отличие от некоторых игрушечных ISA)