Divisi dan modulo pada unsigned integers dengan 6 register

Question

Saya harus menemukan algoritma waktu log (untuk mesin virtual) menggunakan maksimal 6 register (a, b, c, d, e, f) untuk membagi dua bilangan bulat tak bertanda N1 dan N2 ([keduanya> = 0] positif atau 0) dimana jika pembagi adalah 0 maka hasilnya 0 dan operasi modulo.

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

dengan perintah seperti

• RESET a -> a = 0
• TAMBAHKAN ab -> a = a + b
• SUB ab -> a = max (0, ab)
• SHR a -> a = lantai (a / 2)
• SHL a -> a = lantai (a * 2)
• INC a -> a + = 1
• DEC a -> a = max (0, a-1)
• JUMP j -> lompat ke baris ke-j
• JZERO xj -> jika x adalah 0 maka lompat ke k + j
• JODD xj -> jika x ganjil maka lompat ke k + j

Apakah ada algoritme yang dapat membantu saya?

Saya hanya dapat memeriksa apakah nilai di reg adalah GANJIL atau NOL.

Terima kasih atas bantuan Anda.

Answer 1

Saturating-kurangi dan jzeromemungkinkan bandingkan untuk kurang dari atau sama (atau lebih besar dari), sehingga Anda dapat menerapkan versi C dari jawaban njuffa di Bagaimana saya bisa mengalikan dan membagi hanya dengan menggeser dan menambah sedikit? yang menghasilkan hasil bagi dan sisa. Karena Anda memiliki add non-saturating, Anda dapat mengimplementasikan wrapping add (dan kemudian melakukan deteksi implementasi manual dengan memeriksa wraparound, seperti yang dilakukan Nathan di C.)

joddmemungkinkan Anda menguji bit rendah, seperti if (x&1), yang memungkinkan Anda menerapkan algoritme perkalian standar juga. Jadi, jika Anda memiliki algoritme pembagian yang hanya memberi Anda hasil bagi, Anda dapat melakukannya remainder = dividend - quotient*divisordengan perkalian waktu log.

---

T&J divisi biner lainnya:

• Bagaimana cara mengalikan dan membagi hanya dengan menggeser dan menambahkan sedikit? -Jawaban lain pada Q&A yang sama, kali ini menggunakan pergeseran untuk "menyelaraskan" bagian paling signifikan dari pembagi dengan dividen sebelum melanjutkan dengan pembagian panjang buku sekolah. Tapi tidak jelas itu aman tanpa integer lebar yang diperpanjang.
• Pembagian bilangan bulat waktu logaritmik hanya menggunakan penambahan dan pengurangan pergeseran bit
• Bagaimana cara menggunakan bit shifting untuk menggantikan pembagian integer?
• Bagilah dengan 10 menggunakan pergeseran bit? melakukan perkalian di setiap langkah, yang hanya bagus jika Anda memiliki perkalian cepat, atau untuk konstanta yang diketahui dengan sedikit set bit sehingga hanya membutuhkan beberapa shift / penambahan. Keuntungan lainnya adalah tidak membutuhkan shift kanan, tetapi Anda memiliki shift yang benar. (Tidak seperti beberapa ISA mainan)