我需要实现一个简单的宏，在没有除法运算符的处理器上找到两个数字的模（想想 ARM）。我可以通过重复减法来使用除法，但我不知道这是否是最有效或最容易使用的。
有什么建议么？代码会更有帮助。这个特殊的类让我们使用 SPARC 的一个子集，所以大多数操作看起来像这样：add r1, r2, rdest.
这个特定的赋值要求检查a mod b == 0除法的余数是否为零。因此，任何有关有效实施的提示或建议都将受到欢迎。
问问题
13656 次
8 回答
10
不知道你被限制在什么确切的操作，但我认为你会做长除法，像这样，在伪代码中：
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)
这些都没有经过测试，并且可能充满了错误。
于 2009-06-02T06:57:22.333 回答
4
我可以想到两种可能的方法。因为这是家庭作业，所以我将仅提及它们，并让您在可行的情况下工作以及如何实现它们：
A/B = 2^(log2(A)-log2(b))：如果你能得到数值的对数，你就可以很接近除法。
二进制长除法：你在做除法之前就学会了如何做十进制长除法，对吧？所以教你的计算机做二进制长除法（实际上二进制应该更容易）。
（编辑：更正 #1.，对数除法方程）
于 2009-06-02T05:57:53.487 回答
3
这并不能直接回答您的问题，但仍然是一个有趣的案例。如果数字是由 2 的幂模取模，则操作可以执行为
x % 2^n = x & (2^n - 1)
其中使用单个 AND 操作，通常是一个或两个循环操作。
更多信息在维基百科
于 2009-06-02T06:06:18.947 回答
3
似乎用 b 减去（或如果 a 为负数则添加）直到你达到或交叉 0 将是一个简单的实现，尽管几乎可以肯定不是最有效的。
于 2009-06-02T06:09:33.717 回答
1
Jweede，我不知道如何解决您的问题，但我在这里找到了一个看似相关的帖子。
于 2009-06-02T05:47:39.803 回答
0
谢谢你的建议！
我开始使用简单的重复减法除法算法来实现这一点。但正如 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
}
于 2009-06-03T01:06:14.100 回答
0
A/B=Q，因此 A=B*Q。我们知道 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 为真，则将该位保持为 1，否则将其置零。继续 MSB->LSB。（但是，您需要能够检测到 B*Q 会溢出。
于 2009-06-03T02:43:59.630 回答
0
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 设置更好的上限，因为您只能从最高有效位开始。
于 2014-02-28T21:25:49.303 回答