一道面试题。
如何实现加法除法?假设它们都是整数。
我的想法
- 自加除数,直到它大于被除数。 每次迭代,保留相加前的求和结果。
- 商是最后一次相加前的求和结果。可以通过加 1 来计算余数,直到
quotient * divisor + reminder == dividend
。
它是O(e^n)
,有什么更好的主意吗?位运算?
最佳答案
将m
除以n
:
int r = m;
int q = 0;
while( r >= n )
{
int k = 1;
int x = n;
int t;
while( ( t = x+x ) < r )
{
x = t;
k += k;
}
q += k;
r -= x;
}
结果是 q
- 商,r
- 余数。
想法是 x+x
与 x*2
相同。
更新:
有些人可能会提示 r -= x
不是加法。
那么我们可以更新算法以不使用减法:
int p = 0;
int q = 0;
while( p+n <= m )
{
int k = 1;
int x = n;
int t;
while( p + ( t = x+x ) < m )
{
x = t;
k += k;
}
q += k;
p += x;
}
结果是 q
- 商。
如果我们需要余数,则按如下方式进行(p
- 上面的输出):
int r = 0;
while( p < m )
{
int x = 1;
int t;
while( p + ( t = x+x ) < m )
{
x = t;
}
r += x;
p += x;
}
结果是 r
- 余数。
该算法显然具有多项式(非指数)运行时间。
关于c++ - 如何实现加法除法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8689674/