如何在 MIPS 汇编中找到没有除法或模运算符的余数

我想找到一种方法来知道一个整数是除以3还是7而不使用除法，因为它在MIPS汇编中非常慢。

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

有一种方法描述为格兰隆德和蒙哥马利 https://gmplib.org/~tege/divcnst-pldi94.pdf需要（奇）除数模的模/乘法逆2**b。 （本文的某些部分已得到改进recently https://gmplib.org/~tege/division-paper.pdf)

除数：(d) = 3, 7（奇数）是一个简单的情况。假设 32 位（无符号）算术，模数的逆2**32 yield 2863311531 (0xAAAAAAAB) and 3067833783 (0xB6DB6DB7)分别。有一个在线计算器here http://www.hackersdelight.org/magic.htm.

我们还需要qmax = (2**32 - 1) / d价值观：0x55555555 and 0x24924924 resp.

测试 32 位（无符号）数字(n)，执行单字乘法 - 即丢弃完整 64 位结果的高位字：q = dinv * n

If (n)可以整除(d), then (q)必须满足：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))    
}

它用几个单字乘法代替了除法/余数。

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