algorithm - 没有除法运算符的处理器上的汇编 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)

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