如何在MIPS汇编中找到无除法或取模运算符的余数 [英] How to find remainder without division or modulo operator in MIPS assembly

问题描述

我想找到一种方法知道整数是否被3或7除而不使用除法，因为它在MIPS汇编中非常慢.

I want to find a way to know if an integer is divided by 3 or 7 without using division, because it is very slow in MIPS assembly.

我做了很多研究，但一无所获.

I have done a lot of research but found nothing.

推荐答案

格兰伦德蒙哥马利(Montgomery)要求除数模(c0)为(奇)除数的模/乘逆. (本文的某些部分已得到改进，最近)

There's a method described by Granlund & Montgomery that requires the modular / multiplicative inverse of the (odd) divisor modulo 2**b. (Some parts of this paper have been improved recently)

除数:(d) = 3, 7(奇数)是一个简单的例子.假设使用32位(无符号)算术，取模2**32的反数分别产生2863311531 (0xAAAAAAAB)和3067833783 (0xB6DB6DB7). 此处.

The divisors: (d) = 3, 7 (odd numbers) are an easy case. Assuming 32 bit (unsigned) arithmetic, the inverses modulo 2**32 yield 2863311531 (0xAAAAAAAB) and 3067833783 (0xB6DB6DB7) respectively. There's an online calculator here.

我们还需要qmax = (2**32 - 1) / d值:0x55555555和0x24924924分别.

We also need the qmax = (2**32 - 1) / d values: 0x55555555 and 0x24924924 resp.

要测试32位(无符号)数字(n)，请执行一个字乘法-即，丢弃完整64位结果的高位字:q = dinv * n

To test a 32 bit (unsigned) number (n), perform a single word multiply - that is, discard the high word of the full 64 bit result: q = dinv * n

如果(n)可被(d)整除，则(q)必须满足:q * d == n 和 q <= qmax.例如，

If (n) is divisible by (d), then (q) must satisfy: q * d == n and q <= qmax. e.g.,

int is_divisible_by_3 (uint32_t n)
{
    uint32_t q = n * 0xAAAAAAAB;
    return (q <= 0x55555555 && (q * 3 == n))    
}

用两个单字乘法替换除法/余数.

Which replaces a division / remainder with a couple of single word multiplications.

并且对于d = 7同样.另外，像gcc这样的现代编译器也会在为MIPS等生成的程序集中对常数除数/模量(例如if (n % 3 == 0) ...)执行类似的优化.

And similarly for d = 7. Alternatively, a modern compiler like gcc will perform a similar optimization for a constant divisor / modulus, e.g., if (n % 3 == 0) ... - in the assembly generated for MIPS, etc.

这篇关于如何在MIPS汇编中找到无除法或取模运算符的余数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！