c++ - How to implement division by addition?

Question

An interview question.

How to implement division by addition? suppose they are all int.

My idea

1. Add divisor to itself until it is larger than dividend. Each iteration, keep the sum result before addition.
2. The quotient is the sum result before the last addition. the remainder can be counted by adding 1 until the quotient * divisor + reminder == dividend.

It is O(e^n), any better ideas? bit operation?

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をご覧ください。

Answer 3

除算を対数成分に分割してから、それらを計算します。