乗算、除算、剰余演算子を使用せずに 2 つの整数を除算します。

この問題では、乗算、除算、剰余演算子を使用せずに、2 つの整数を除算するだけで済みます。ただし、加算、乗算、またはビット演算を使用できます。

問題文では、2 つの整数 x と y を取得すると述べています。乗算、除算、またはモジュロ演算子を使用せずに、x を y で割った商を求める必要があります。

＃＃＃例＃＃＃

入力

: x=15、y=5

出力

: 3

入力

: x=10、y=4

出力

: 2

入力

: x=-20、y=3

出力

:-6 ＃＃＃方法＃＃＃ 方法 1 (単純な計算を使用)

この方法では、単純な数学的アルゴリズムを使用します。ここでは、私たちが従うべきことを段階的に説明します -

x が y 以上になるまで、被除数 (つまり x) から除数 (つまり y) を減算し続けます。

• y が x より大きい場合、つまり除数が被除数より大きい場合、被除数は剰余となり、減算の回数は商となります。

• 減算が実行された回数を変数に格納して返します。これが必要な出力です。

• ＃＃＃例＃＃＃

  以下は、上記のアルゴリズムの C 実装です &minnus;

  リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量: O(a/b)

空間複雑度: O(1)

方法 2 (ビット演算を使用)

任意の数値は 0 または 1 の形式で表現できるため、商はシフト演算子を使用して 2 進形式で表現できます。

for ループを使用して、除数のビット位置を 31 から 1 まで繰り返します。

• 除数 (b

• 次の位置を検証するときは、結果を temp 変数に追加して、temp (b

• 商を計算するたびに商を更新しますOR

1

対応するシンボルを更新した後、商に戻ります。

• ＃＃＃例＃＃＃ 以下は、上記のメソッドの C 実装です - リーリー ＃＃＃出力＃＃＃ リーリー

• 時間計算量: O(log(a))

スペースの複雑さ: O(1)、

余分なスペースを使用しないため。

方法 3 (対数関数を使用)

この方法では、単純な対数関数を使用して商を計算します。

誰もが知っているように、 $$\mathrm{In(\frac{a}{b})\:=\:In(a)\:-\:In(b)}$$

はさらに に変更できます。 $$\mathrm{\frac{a}{b}\:=\:e^{(In(a)\:-\:In(b))}}$$

これが、この効率的な方法を使用して特定の問題を解決するための基本的なアイデアです。

以下は、私たちが従う方法の段階的な説明です -

それらのいずれか (つまり、被除数または除数) が 0 の場合、0 を返します。

次に、排他的論理和関数 (XOR) を使用してシンボルをチェックし、シンボルを変数に格納します。

除数が 1 の場合、被除数は直接返されます。

• 次に、変数を宣言し、

  exp
関数と
• log

  関数を使用します。

• Log と exp は C の組み込み関数です。 log 関数は入力数値の自然対数を返し、exp は e に入力値を加えた値に等しい値を返します。

• ＃＃＃例＃＃＃

  以下は、上記のメソッドの C 実装です - リーリー ＃＃＃出力＃＃＃ リーリー 時間計算量: O(1)、、この操作の実行には一定の時間がかかるため。

• スペースの複雑さ: O(1)、

  余分なスペースを使用しないため。

  ＃＃＃結論は＃＃＃
この記事では、乗算、除算、または剰余演算子を使用せずに 2 つの整数を除算する方法を学習します。私たちは、さまざまな効率でさまざまな方法で問題を解決することを学びました。単純な数学、ビット演算、対数関数を使用します。このうち、対数関数を使用する方法は、計算量が O(1) と全方法の中で最も小さいため、最も効率的な方法です。

この記事がこのトピックに関するすべての概念の解決に役立つことを願っています。

以上が乗算、除算、剰余演算子を使用せずに 2 つの整数を除算します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。