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

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是位数）。有一些方法，如 Newton-Raphson 或倒数计算，它们基于乘法，其中的迭代次数为O(log n). 看看http://en.wikipedia.org/wiki/Division_%28digital%29

Answer 3

您可以将除法分解为其对数分量，然后计算这些分量。

Answer 4

对于 int 数字，您可以使用以下逻辑：

16 除以 5 = 3 (i)

i=1 -> 5+0 = 5 < 16
i=2 -> 5+5 = 10 < 16
i=3 -> 5+5+5 = 15 < 16
i=4 -> 5+5+5+5 = 20 > 16

所以 3 将是你的答案。