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

Question

我正在编写一个MIPS不能使用浮点计算 IE 模、除法、乘法的库。

我已经用 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;
}

但是，这种方法效率很低。一种更复杂但更快的方法是使用二进制长除法。这类似于常规的长除法，除了在二进制中每一步的结果是0或者1而不是0..9。使用 BLD进行计算的基本方法x % y如下所示：

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

上面的一个问题：必须在whendivisor <= INT_MAX/2中停止溢出。divisor <<= 1x > 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).

Answer 2

二进制长除法可以解决问题：

16 / 3 的示例（二进制 10000 ₂ / 11 ₂）：

 10000 | Quotient
 1     | 0         // 1 < 11 (append 0 to quotient, no effect)
 10    | 0         // 10 < 11 (append 0 to quotient, no effect)
 100   | 1         // 100 > 11, append 1 to quotient
- 11   | 
----   |
   1   |
   10  | 10        // 10 < 11, append 0 to quotient
   100 | 101       // 100 > 11, append 1 to quotient
 -  11 | 101
 ----- |
     1 | 101       // Quotient = 101, Remainder = 1

由于结果是二进制的，因此您可以立即判断何时将 0 或 1 附加到商：当先前计算的片段小于除数时，则附加 0；当片段大于除数时，追加1。

Answer 3

我用 C 语言编写了除法和乘法函数，然后将该代码翻译成 MIPS。

我猜你写的除法函数可能已经在算法结束时计算了模数 x%N。出于这个原因，像 x86 这样的高级架构提供了同时返回 x/N 和 x%N 的汇编指令（例如 divl）：通常用于计算一个的任何算法都会自动给出另一个，所以你可以杀死两只鸟如果同时需要两者，则用一块石头。

此外，如果您编写了除法和乘法函数，那么您就拥有了计算模数所需的一切，因为x%N == x - N*( x/N ). 所以在最坏的情况下，如果你想只使用加减法计算 x%N，并且你知道如何只使用加减法进行乘除，那么你可以使用上面的公式得到 x%N。话虽如此，您可以做得比这更好，例如通过已经建议的长除法。

Answer 4

虽然不如上面的实现高效，但如果在面试中问过这个问题，这里有一个 JavaScript 中的快速递归解决方案。请注意，这也支持负数和十进制输入。

var modulo = function(x, y) {
    y = Math.abs(y);
    return (x < y) ? x : modulo(x - y, y);
};

console.log(modulo(12, 5)); //2
console.log(modulo(10, 2)); //0
console.log(modulo(4, 10)); //4
console.log(modulo(4, 2.4)); //1.6
console.log(modulo(-1, 10)); //-1
console.log(modulo(10, -3)); //1
console.log(modulo(10, -4)); //2
console.log(modulo(10, -3)); //1