无分割算子的处理器装配模型算法

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)

这些都没有经过测试,而且可能存在错误.