algorithm - srt除算 アルゴリズム




'/'を使用しない除算 (11)

'/'演算子を使用しないintの単純な除算方法を次に示します。

public static int divide(int numerator, int denominator) throws Exception {

    int q = 0;
    boolean isNumPos = (numerator >= 0) ? true : false;
    boolean isDenPos = (denominator >= 0) ? true : false;

    if (denominator == 0) throw new Exception("Divide by 0: not an integer result");

    numerator = Math.abs(numerator);
    denominator = Math.abs(denominator);

    while (denominator <= numerator) {
        numerator -= denominator;
        q++;
    }

    return (isNumPos ^ isDenPos) ? -q : q;
}

誰も私に '/'を使わないで除算演算を実行する効率的なアプローチを教えてもらえますか? バイナリ検索に似た方法を使って、 log(n)ステップで整数値を計算することができます。

115/3 
57 * 3 > 115
28 * 3 < 115
47 * 3 > 115
.
.
.
38 * 3 is quotient value .....

しかし、他のより効率的な方法がありますか?


2つの数字を使用せずに/

int div(int a,int b){

    if(b == 0)
         return -1;   //undefined
    else if (b == 1)
         return a;    
    else if(b > 1){

       int count = 0;
       for(int i=b;i<=a;i+=b){
           count++;
       }
    }

    return count;

}

OPはそれがインタビューの質問だと言ったので、面接者はあなたのコーディングスキルに加えて、次のことを見たいと思う。 (Javaを使用していると仮定します)

  1. 負の数値を扱うには? 被除数と除数の両方を正の数に変換するのは一般的です。 しかし、 Math.abs(Integer.MIN_VALUE)はまだInteger.MIN_VALUEことを忘れるかもしれません。 したがって、配当がInteger.MIN_VALUEの場合、別々に計算する必要があります。

  2. "Integer.MIN_VALUE / -1"の結果はどうですか? Integerにはそのような値はありません。 インタビュアーと話し合う必要があります。 この条件の例外をスローすることができます。

以下はこの質問のJavaコードです。それを検証するにはleetcode:2つの整数を除算しください

public int divide(int dividend, int divisor) {

    if(divisor == 0)
        throw new Exception("Zero as divisor!");

    int a = Math.abs(dividend);
    int b = Math.abs(divisor);

    boolean isPos = true;
    if(dividend < 0) isPos = !isPos;
    if(divisor < 0) isPos = !isPos;

    if(divisor == Integer.MIN_VALUE){

        if(dividend == Integer.MIN_VALUE) return 1;
        else return 0;
    }

    if(dividend == Integer.MIN_VALUE) {

        if(divisor == -1){

            // the result is out of Integer's range.
            throw new Exception("Invalid result.");
        } else {
            // Because Math.abs(Integer.MIN_VALUE) = Integer.MIN_VALUE
            // we avoid it by adding a positive divisor to Integer.MIN_VALUE
            // here I combined two cases: divisor > 0 and divisor < 0
            return divide((dividend + b), divisor) - divisor/b;
        }
    }

    int res = 0;        
    int product = b;

    while(a >= b){

        int multiplier = 1;
        while(a - product >= product){

            product = product << 1;// "product << 1" is actually "product * 2"
            multiplier = multiplier << 1;
        }
        res += multiplier;
        a -= product;
        product = b;
    }

    return isPos?res:-res;

}

これは、乗算の使用を許可されていない問題の解決策です )。

私はこの解決策が好きです: https://.com/a/5387432/1008519 ://.com/a/5387432/1008519、しかし、私はそれをやや難しいと思っています(特に| -part)。 この解決策は私の頭の中でもう少し意味をなさない:

var divide = function (dividend, divisor) {
  var result = 1;
  var denominator = divisor;
  // Double denominator value with bitwise shift until bigger than dividend
  while (dividend > denominator) {
    denominator <<= 1;
    result <<= 1;
  }

  // Minus divisor value until denominator is smaller than dividend
  while (denominator > dividend) {
    denominator -= divisor;
    result -= 1;
  }

  return result;
}
  1. 我々は結果を1に初期化する(配分よりも大きくなるまで分母を倍にするので)
  2. 配当よりも大きくなるまで分母を(ビットシフトで)倍にする
  3. 私たちの分母が私たちの配当よりも大きいことを知っているので、私たちの配当は配当を下回るまでマイナスできます
  4. 分母を使ってできるだけ分母が結果に近いので、結果を返します。

いくつかのテストがあります:

console.log(divide(16, 3)); // 5
console.log(divide(16, 33)); // 0
console.log(divide(972, 5)); // 194
console.log(divide(384, 15)); // 25

ここでは、0除数の場合と負の配当および/または除数の両方を扱う要点がありhttps://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130https://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130 : https://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130


おそらく、他のビット演算子で>>(ビットシフト)のシーケンスを使用して行う方法を工夫することができます。 Wikipediaの擬似コードの例があります Bitwise Operatorの記事。


これは私の問題を解決した関数です:

func printRemainderAndQuotient(numerator: Int,divisor: Int) {
  var multiplier = 0
  var differene = numerator - divisor
  var dynamicNumber = 0
  if divisor == 0 {
    print("invalid divisor")
    return
  }
  if divisor == numerator {
    print("quotient : " + "1")
    print("remainder : " + "0")
    return
  }
  while differene >= divisor {
    multiplier = multiplier + 1
    dynamicNumber = divisor * multiplier
    differene = numerator - dynamicNumber
  }
  print("quotient : " + "\(multiplier)")
  print("remainder : " + "\(differene)")
}

まあ、見てみましょう... x / y = e ^(ln(x)-ln(y))


主なコンセプト:

私たちがcalc 20/4だから

4*(1+1) = 8 *(1+1) = 16 *(1+1) == 32 (which is bigger) X
so go back to 16 and try 16*(1+0.5) == 24 (bigger) X
so go back to 16 and try 16*(1+0.25) == 20 

コード:

float product=1,multiplier=2,a=1;
int steps=0;

void divCore(float number, float divideBy,float lastDivison)
{
    steps++;
    //epsilon check e.g (10/3) will never ends
    if(number - divideBy < 0.01)
        return;
    else
    {
        lastDivison = divideBy; 
        divideBy *= multiplier;
        if(number >= divideBy)
        {
            product *= multiplier;
            divCore(number,divideBy,lastDivison);
        }
        else
        {
            a *= 0.5;
            multiplier = 1 + a;
            divCore(number,lastDivison,lastDivison);
        }
    }
}

float Divide(float numerator, float denominator)
{
    //init data
    int neg=(numerator<0)?-1:1;
    neg*=(denominator<0)?-1:1;
    product = 1;
    multiplier = 2;
    a = 1;
    steps =0;
    divCore(abs(numerator),abs(denominator),0);
    return product*neg;
}

典型的な方法は、シフトと減算です。 これは、学校で学んだときと基本的にはかなり同じです。 大きな違いは、小数点以下の桁では、結果の次の桁を見積もる必要があることです。 バイナリでは、それは簡単です。 次の桁は常に0または1のいずれかです。(左シフトの)除数が現在の被除数の値以下であれば、それを減算し、結果の現在のビットは1になります。結果の現在のビットは0です。コードは次のようになります。

unsigned divide(unsigned dividend, unsigned divisor) { 

    unsigned denom=divisor;
    unsigned current = 1;
    unsigned answer=0;

    if ( denom > dividend) 
        return 0;

    if ( denom == dividend)
        return 1;

    while (denom <= dividend) {
        denom <<= 1;
        current <<= 1;
    }

    denom >>= 1;
    current >>= 1;

    while (current!=0) {
        if ( dividend >= denom) {
            dividend -= denom;
            answer |= current;
        }
        current >>= 1;
        denom >>= 1;
    }    
    return answer;
}

これは、私たちが手で長時間に分割するときと同じように機能します。 たとえば、972/5を考えてみましょう。 小数点の長い区分では、次のようなことを行います。

 ____ 
5)972

次に、各桁を個別に計算します。 5は9に1回入るので、答えのその桁に1を書き留め、被除数の(その桁から)1 * 5を減算し、被除数の次の桁を「下げる」:

  1
 ----
5)972
  5
  ---
  47

私たちはすべての数字を記入するまで同じことを続けます:

   194
  ----
 5)972
   5
   ---
   47
   45
   ---
    22
    20
   ---
     2

だから、私たちの答えは194余りです2。

さて、同じことをバイナリで考えてみましょう。 バイナリで972は11 1100 1100であり、5は101 。 バイナリと小数で除算を行うことには1つの基本的な違いがあります。小数点以下の桁は0〜9のいずれかになるため、乗算して中間結果を求めなければなりません。 バイナリでは、数字は0または1にしかなりません。なぜなら、0または1(これは通常、if文で処理します。 )。

   -----------
101)1111001100

だから、私たちの最初のステップは、結果の最初の数字がどれになるかを調べることです。 私たちは101と1111001100を比較し、それが大きくなるまでそれを左にシフトすることでそれを行います。 それは私たちに与えます:

  |
 1111001100
10100000000

そのようにシフトすると、移動した場所の数がカウントされ、結果のどの桁がいつ入力されるかがわかります。 私は上の縦棒でそれを示しました。 次に、中間結果を右に1つシフトし、垂直バーを右にシフトして、結果桁を埋めるために行っていることを示します。

    |
  1111001100
  1010000000

そこから、シフトされた除数が被除数より小さいかどうかがチェックされます。 そうであれば、答えの適切な場所に1を記入し、中間結果からシフトされた除数を減算します[そして、列を真っ直ぐに保つのに役立ちます]いくつかのスペースを挿入します:

        1  
     -----------------------------
  101)1  1  1  1  0  0  1  1  0  0
      1  0  1  0  0  0  0  0  0  0
      ----------------------------
      1  0  1

私たちは同じ方法を続け、結果の数字を記入し、すべての数字を入力するまで中間結果からシフトした除数を減算します。 物事をまっすぐに保つためのさらなる試みでは、結果の各桁に、減数の隣の右端に書くつもりです:

            1  1  0  0  0  0  1  0
     -----------------------------
  101)1  1  1  1  0  0  1  1  0  0
      1  0  1                             1
      -----------------------------
         1  0  1
         1  0  1                           1
      -----------------------------
            0  0  0                          0
         --------------------------
               0  0  0                        0
          -------------------------
                  0  0  1                      0
          -------------------------
                     0  1  1                    0
          -------------------------
                        1  1  0   
                        1  0  1                   1
           ------------------------
                           0  1  0                 0

したがって、11000010、残りの10の結果が得られます。これらを10進数に変換すると、予想される194と2がそれぞれ得られます。

上記のコードとの関連性を考えてみましょう。 除数を配当よりも大きくなるまで左にシフトさせることから始めます。 次に、右シフトを繰り返しシフトし、その値が最後の減算後に得られた中間値よりも小さいかどうかをチェックします。 それが少ない場合は、再び減算し、その数字の1を入力します。 それが大きい場合は、結果のその桁に「0を引いて(何もしない)」と「0」を記入します(何もしないでください)。 0の)。

すべての桁を埋めると、それが結果であり、残っている金額はまだ残っていません。

なぜコード内で+=代わりに|=を使用したのかという質問があります。 私はこれが理由を説明するのを助けることを望む このケースでは同じ結果が得られますが、私は既存の部分的な答えに各数字を加えることは考えていません。 むしろ、私はそれが答えの中に空であると思って、それがちょうどそれを埋めると思っています。


基本的な高校の数学を使った単純なPython実装。 分母は、単に負の1の冪乗の数である。

def divide(a, b):
    return a * b ** -1

    private int divideBy2(int number){

    int count = 1;
    while(count<=number){

        if(count*2==number){

            return count;
        }
        count++;
    }
    return count;

}




division