Division et modulo sur des entiers non signés avec 6 registres

Dec 02 2020

Je dois trouver un algorithme de temps de journalisation (pour une machine virtuelle) utilisant au maximum 6 registres (a, b, c, d, e, f) pour diviser deux entiers non signés N1 et N2 ([les deux sont> = 0] positifs ou 0) où si le diviseur est 0, le résultat est 0 et l'opération modulo.

  • div -> N1 / N2
  • mod -> N1% N2

avec des commandes comme

  • RÉINITIALISER a -> a = 0
  • AJOUTER ab -> a = a + b
  • SUB ab -> a = max (0, ab)
  • SHR a -> a = plancher (a / 2)
  • SHL a -> a = plancher (a * 2)
  • INC a -> a + = 1
  • DEC a -> a = max (0, a-1)
  • JUMP j -> passer à la j-ième ligne
  • JZERO xj -> si x est 0 alors sautez à k + j
  • JODD xj -> si x est impair alors passer à k + j

Y a-t-il des algorithmes qui peuvent m'aider?

Je ne peux que vérifier si la valeur dans reg est ODD ou ZERO.

Merci pour l'aide.

Réponses

1 PeterCordes Dec 02 2020 at 18:34

Saturer-soustraire et jzeropermet de comparer pour inférieur ou égal (ou supérieur à), afin que vous puissiez implémenter la version C de la réponse de njuffa sur Comment puis-je multiplier et diviser en utilisant uniquement le décalage de bits et l'ajout? qui produit le quotient et le reste. Comme vous avez un ajout non saturant, vous pouvez implémenter l'ajout de wrapping (puis effectuer une détection manuelle du report en vérifiant le wraparound, comme Nathan le fait en C.)

joddvous permet de tester le bit faible, comme if (x&1), qui vous permettrait également d'implémenter l'algorithme de multiplication standard. Donc, si vous aviez un algorithme de division qui ne vous donnait qu'un quotient, vous pourriez faire remainder = dividend - quotient*divisoravec une multiplication log-temps.


Autres questions et réponses sur la division binaire:

  • Comment puis-je multiplier et diviser en utilisant uniquement le décalage et l'ajout de bits? -une autre réponse sur le même Q&A, cette fois en utilisant des décalages pour «aligner» le bit le plus significatif du diviseur avec le dividende avant de procéder à la division longue des manuels scolaires. Mais il n'est pas clair que ce soit sûr sans les entiers de largeur étendue.
  • Division logarithmique des entiers temporels en utilisant uniquement l'addition et la soustraction de décalage de bits
  • Comment puis-je utiliser le décalage de bits pour remplacer la division entière?
  • Diviser par 10 en utilisant des décalages de bits? fait une multiplication à chaque étape, ce qui n'est bon que si vous avez une multiplication rapide, ou pour des constantes connues avec quelques bits définis, cela ne prend donc que quelques décalages / ajouts. Un autre avantage ne nécessite pas de décalage à droite, mais vous avez un décalage à droite. (Contrairement à certains ISA jouets)