仅使用加法/减法编写模数函数

Question

我正在写一个库MIPS,我不能使用浮点计算IE模数,除法,乘法.

我在C中编写了除法和乘法函数,然后我将该代码翻译成了MIPS.

然而,我迷失了如何通过C仅使用加法或减法来编写函数来计算模数.

如何使用ONLY加法和减法编写一个函数来计算模数？

Answer 1

注意:以下代码片段仅在两个操作数都为正时才有效.我省略了对负值的任何处理,因为x % y当一个或两个操作数为负时的结果在不同的语言和平台之间有所不同.通常,您可以计算abs(x) % abs(y)然后对结果执行某些转换.

x % y仅使用加法和减法计算的最简单方法是重复减去,y直到剩余值小于y:

/* Compute x mod y naively. */
int mod_basic(int x, int y) {
    int result = x;   
    while (result >= y)
        result -= y;

    return result;
}

但是,这种方法效率很低.更复杂但更快的方法是使用二进制长除法.这类似于常规长除法,除了二进制之外,每一步的结果是0或者1代替0..9.x % y使用BLD 计算的基本方法如下所示:

/* Compute x mod y using binary long division. */
int mod_bld(int x, int y)
{
    int modulus = x, divisor = y;

    while (divisor <= modulus && divisor <= INT_MAX/2)
        divisor <<= 1;

    while (modulus >= y) {
        while (divisor > modulus)
            divisor >>= 1;
        modulus -= divisor;
    }

    return modulus;
}

上面有一个问题:divisor <= INT_MAX/2必须在divisor <<= 1什么时候停止溢出x > MAX_INT/2.

另外divmod,在一次计算中给出了商和模数,看起来几乎完全相同:

/* Compute divmod(x, y) using binary long division. */
void divmod(int x, int y, int *div, int *mod) {
    int quotient = 0, modulus = x, divisor = y;

    while (divisor <= modulus && divisor <= INT_MAX/2)
        divisor <<= 1;

    while (modulus >= y) {
        while (divisor > modulus) {
            divisor >>= 1;
            quotient <<= 1;
        }

        modulus -= divisor;
        quotient++;
    }

    while (divisor != y) {
        quotient <<= 1;
        divisor >>= 1;
    }

    *div = quotient;
    *mod = modulus;
}

最后,请注意,如果y是2的幂,你可以作弊.在这种情况下x % y只是x & (y - 1).