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

Question

我正在为 MIPS 编写一个库，我不能使用浮点计算 I.E.模数、除法、乘法。

我用 C 编写了除法和乘法函数，然后将代码转换为 MIPS。

但是，我不知道如何通过 C 仅使用加法或减法编写一个函数来计算模数。

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

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;
}

但是，这种方法效率很低。一个更复杂但更快的方法是使用 binary long division .这类似于常规的长除法，除了在二进制中每一步的结果是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) .