c++ - 如何实现加法除法？

Question

一道面试题。

如何实现加法除法？假设它们都是整数。

我的想法

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

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