如何通过添加实现除法？

Question

面试问题.

如何通过添加实现除法？假设他们都是int.

我的想法

1. 添加除数给它自己,直到它大于被除数.每次迭代,在添加之前保留总和结果.
2. 商是最后一次加法之前的总和结果.剩余部分可以加1来计算quotient * divisor + reminder == dividend.

这是O(e^n)什么更好的想法？位操作？

Answer 1

将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- 余数。

该算法显然具有多项式（非指数）运行时间。

Answer 2

在数字算术中，我们可以将恢复和非恢复方法称为基于加法/减法的简单除法算法。这些方法中的迭代次数为O(n)（其中n是位数）。有一些方法，如牛顿拉夫森或倒数计算，它们基于乘法，其中迭代次数为O(log n)。看看http://en.wikipedia.org/wiki/Division_%28digital%29