Divisione e modulo su interi senza segno con 6 registri

Question

Devo trovare l'algoritmo del tempo di log (per una macchina virtuale) utilizzando al massimo 6 registri (a, b, c, d, e, f) per dividere due interi senza segno N1 e N2 ([entrambi sono> = 0] positivo o 0) dove se divisore è 0, il risultato è 0 e l'operazione modulo.

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

con comandi come

• RESET a -> a = 0
• AGGIUNGI ab -> a = a + b
• SUB ab -> a = max (0, ab)
• SHR a -> a = floor (a / 2)
• SHL a -> a = floor (a * 2)
• INC a -> a + = 1
• DEC a -> a = max (0, a-1)
• JUMP j -> salta alla j-esima riga
• JZERO xj -> se x è 0 allora salta a k + j
• JODD xj -> se x è dispari di salta a k + j

Esistono algoritmi che possono aiutarmi?

Posso solo controllare se il valore in reg è DISPARI o ZERO.

Grazie per il tuo aiuto.

Answer 1

Saturating-subtract e jzeroconsente il confronto per minore o uguale (o maggiore di), quindi puoi implementare la versione C della risposta di njuffa su Come posso moltiplicare e dividere usando solo lo spostamento e l'aggiunta di bit? che produce quoziente e resto. Poiché hai l'aggiunta non saturante, puoi implementare l'aggiunta di avvolgimento (e quindi eseguire il rilevamento manuale dell'esecuzione controllando l'avvolgimento, come fa Nathan in C.)

joddti consente di testare il bit basso, come if (x&1), che ti consentirebbe di implementare anche l'algoritmo di moltiplicazione standard. Quindi, se avessi un algoritmo di divisione che ti dava solo un quoziente, potresti farlo remainder = dividend - quotient*divisorcon una moltiplicazione log-temporale.

---

Domande e risposte su altre divisioni binarie:

• Come posso moltiplicare e dividere usando solo lo spostamento e l'aggiunta di bit? -un'altra risposta sulla stessa domanda e risposta, questa volta utilizzando i turni per "allineare" la parte più significativa del divisore con il dividendo prima di procedere con la divisione lunga del libro di scuola. Ma non è chiaro che sia sicuro senza numeri interi a larghezza estesa.
• Divisione del tempo intero logaritmico utilizzando solo l'addizione e la sottrazione di spostamento di bit
• Come posso usare il cambio di bit per sostituire la divisione intera?
• Dividere per 10 usando gli spostamenti di bit? esegue una moltiplicazione in ogni passaggio, il che è utile solo se si dispone di una moltiplicazione rapida o per costanti note con pochi bit impostati in modo che siano necessari solo un paio di spostamento / aggiunta. Un altro vantaggio non è richiedere un cambio di destra, ma hai un turno di destra. (A differenza di alcuni ISA giocattolo)