没有除法运算符的处理器上的汇编 mod 算法

Question

我需要实现一个简单的宏，用于在没有除法运算符的处理器（例如 ARM）上查找两个数字的模。 我可以通过重复减法来使用除法，但我不知道这是否是最有效或最容易使用的。

有什么建议么？ 代码会更有帮助。 这个特定的类让我们使用 SPARC 的子集，因此大多数操作如下所示：add r1, r2, rdest。

这个特定的赋值要求检查a mod b == 0或者除法的余数是否为零。 因此，任何有关有效实施的提示或建议都将受到欢迎。

Answer 1

不知道你限制的具体操作是什么，但我认为你会用伪代码进行长除法，如下所示：

dividend = abs(dividend)
divisor = abs(divisor)
if divisor == 0,
    barf
remainder = dividend
next_multiple = divisor

do
    multiple = next_multiple
    next_multiple = left_shift(multiple, 1)
while next_multiple <= remainder && next_multiple > multiple

while multiple >= divisor,
    if multiple <= remainder,
        remainder = remainder - multiple
    multiple = right_shift(multiple, 1)

要实际计算商（或至少其绝对值），最后一部分将是类似于：

quotient = 0
while multiple >= divisor,
    quotient = left_shift(quotient, 1);
    if multiple <= remainder,
        remainder = remainder - multiple
        quotient = quotient + 1
    multiple = right_shift(multiple, 1)

这些都没有经过测试，并且可能充满错误。

Answer 2

这并没有直接回答您的问题，但仍然是一个有趣的案例。 如果该数字以 2 的幂为模，则该运算可以执行为

x % 2^n = x & (2^n - 1)

使用单个 AND 运算，通常是一个或两个周期运算。

更多信息维基百科

Answer 3

我可以想到两种可能的方法。 因为这是家庭作业，所以我只会提及它们，并让您工作（如果它们可行）以及如何实现它们：

1. A/B = 2^(log2(A)-log2(b))：如果您可以获得对数

2. 二进制长除法：在进行除法之前，您已经学会了如何进行十进制长除法，对吧？ 所以教你的计算机进行二进制长除法（实际上二进制应该更容易）。

（编辑：更正#1，对数除法方程）

Answer 4

似乎用 b 减去（或加，如果 a 为负数）直到达到或跨越 0 将是一个简单的实现，尽管几乎肯定不是最有效的。

Answer 5

Jweede，我不知道如何解决你的问题，但我发现了一个看似相关的帖子 在这里。

Answer 6

A/B=Q，因此A=B*Q。 我们都知道 A 和 A 。 B，我们想要 Q。

我的想法是：
二分查找 Q。从 Q=0 & 开始 Q=1，也许作为基本情况。 继续加倍直到B*Q> A，然后你就有了两个界限（Q 和 Q/2），所以找到这两个界限之间的正确 Q。 O(log(A/B))，但实现起来有点棘手：

#include <stdio.h>
#include <limits.h>
#include <time.h>

// Signs were too much work.
// A helper for signs is easy from this func, too.
unsigned int div(unsigned int n, unsigned int d)
{
    unsigned int q_top, q_bottom, q_mid;
    if(d == 0)
    {
        // Ouch
        return 0;
    }

    q_top = 1;
    while(q_top * d < n && q_top < (1 << ((sizeof(unsigned int) << 3) - 1)))
    {
        q_top <<= 1;
    }
    if(q_top * d < n)
    {
        q_bottom = q_top;
        q_top = INT_MAX;
    }
    else if(q_top * d == n)
    {
        // Lucky.
        return q_top;
    }
    else
    {
        q_bottom = q_top >> 1;
    }

    while(q_top != q_bottom)
    {
        q_mid = q_bottom + ((q_top - q_bottom) >> 1);
        if(q_mid == q_bottom)
            break;

        if(d * q_mid == n)
            return q_mid;
        if(d * q_mid > n)
            q_top = q_mid;
        else
            q_bottom = q_mid;
    }
    return q_bottom;
}

int single_test(int n, int d)
{
    int a = div(n, d);
    printf("Single test: %u / %u = %u\n", n, d, n / d);
    printf(" --> %u\n", a);
    printf(" --> %s\n", a == n / d ? "PASSED" : "\x1b[1;31mFAILED\x1b[0m");
}

int main()
{
    unsigned int checked = 0;
    unsigned int n, d, a;

    single_test(1389797028, 347449257);
    single_test(887858028, 443929014);
    single_test(15, 5);
    single_test(16, 4);
    single_test(17, 4);
    single_test(0xFFFFFFFF, 1);

    srand(time(NULL));

    while(1)
    {
        n = rand();
        d = rand();

        if(d == 0)
            continue;

        a = div(n, d);
        if(n / d == a)
            ++checked;
        else
        {
            printf("\n");
            printf("DIVISION FAILED.\n");
            printf("%u / %u = %u, but we got %u.\n", n, d, n / d, a);
        }

        if((checked & 0xFFFF) == 0)
        {
            printf("\r\x1b[2K%u checked.", checked);
            fflush(stdout);
        }
    }

    return 0;
}

此外，您还可以迭代这些位，将每个位设置为 1。如果 B * Q <= A 为 true，则将该位保持为 1，否则将其归零。 继续MSB→LSB。 （但是，您需要能够检测到 B*Q 是否会溢出。

Answer 7

谢谢你的建议！

我开始使用简单的除法重复减法算法来实现这一点。 但正如 ysth 所指出的，还有一种更简单的方法。 这是第一个算法：

        .macro mod a, b, r
        mov a, r
divlp:  sub r, b, r
        cmp r, b
        bge divlp
        .endmacro

这非常类似于：

mod(a, b){
   int r = a
   while(r >= b){
      r = r - b
   }
   return r
}

Answer 8

mod 可以一点一点地计算：

int r = 0;
int q = 0;
for (int i = sizeof(n) * 8 - 1; i >= 0; --i) {
  r <<= 1;
  r |= (n >> i) & 1;
  if (r > d) {
    r -= d;
    q |= 1 << i;
  }
}
return r;

得到余数，q 就是商。
如果您有 bsrl 指令，您可以为 i 设置更好的上限，因为您只能从最高有效位开始。