C++での符号なし整数の除算アルゴリズムの復元

除算アルゴリズムを使用して符号なし整数を除算する方法について説明します。一部の除算アルゴリズムは紙に適用され、その他はデジタル回路に実装されます。除算アルゴリズムには、低速除算アルゴリズムと高速除算アルゴリズムの2種類があります。低速除算アルゴリズムには、復元、非実行復元、SRT、および非復元アルゴリズムが含まれます。

このチュートリアルでは、0<除数<被除数

解決策を見つけるためのアプローチ

ここでは、レジスタQを使用して商を格納し、レジスタAを使用して剰余を格納し、Mを使用して除数を格納します。 Aの初期値は0に保たれ、その値が復元されます。そのため、このメソッドは除算を復元しています。

• レジスタを値で初期化します

  • Q=配当

  • A =0、

  • M =除数、

  • N=配当のビット数。

• 左シフトAQは、レジスタAとQを単一のユニットとして使用することを意味します。

• AをMで減算し、Aに格納します。

• Aの最上位ビットを確認してください：

  • 0の場合、最下位ビットを1に設定します。

  • それ以外の場合は、最下位ビットを0に設定します。

• Aの値を復元し、カウンターNの値をデクリメントします。

• N =0の場合、ループを解除します。それ以外の場合は、手順2に進みます。

• 商はレジスタQに格納されます。

フローチャート

例

上記のアプローチのC++コード

#include <iostream>
using namespace std;
int main(){
   // initializing all the variables with Dividend = 9, Divisor = 2.
   int Q = 8,q=1,M=3;
   short N = 4;
   int A = Q;
   M <<= N;
   // loop for division by bit operation.
   for(int i=N-1; i>=0; i--) {
      A = (A << 1)- M;
      // checking MSB of A.
      if(A < 0) {
         q &= ~(1 << i);  // set i-th bit to 0
         A = A + M;
      } else {
         q |= 1 << i;     // set i-th bit to 1
      }
   }
   cout << "Quotient: "<< q;
   return 0;
}

出力

Quotient: 2

結論

このチュートリアルでは、符号なし整数の除算アルゴリズムの復元について説明しました。フローチャートとビット演算の適用を利用して、この問題を解決するための簡単なアプローチについて説明しました。また、C、Java、Pythonなどのプログラミング言語で実行できるこの問題のC++プログラムについても説明しました。このチュートリアルがお役に立てば幸いです。