0

私は 32 ビットの 2 進乗算器の C++ 実装を試していました。私はこれを行う方法を1つだけ知っています

    1011   (this is 11 in decimal)      
x   1110   (this is 14 in decimal)      
   ======        
    0000   (this is 1011 x 0)       
   1011    (this is 1011 x 1, shifted one position to the left)      
  1011     (this is 1011 x 1, shifted two positions to the left)     
 1011      (this is 1011 x 1, shifted three positions to the left)   
=========    
10011010   (this is 154 in decimal).

より長い2進数で操作を行う必要があるため、コーディングがそれほど面倒ではない別の方法はありますか?

4

4 に答える 4

0

ブースの乗算アルゴリズムを使用できます。ウィキペディアに関する詳細情報があります: http://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm

于 2013-04-08T12:47:15.983 に答える
0

はい、ループを使用してこれを実現できます。タイプが 32 ビットであると仮定すると、longlong*long の結果は 64 ビットになります。

たとえば、long Aアリ along Bがあり、計算したい場合a*b

まず、結果を として定義しますlong long result = 0;。次に、B のすべてのビットをチェックし、ビットが 1 の場合、A << Xresult に追加します。ここで、X はビットのインデックスです。1 つのループでこれを実現できます。

long long AA = A;// convernt A to AA to avoid overflow
for( int index=0;i<32;++index )
{
    if( B & 0x1 )
        result += AA;
    AA <<= 1;
    B >>= 1;
}

私が間違いを犯していないことを願っています。このアイデアがあなたの役に立ちます。

于 2013-04-08T13:11:46.983 に答える
0

まあ、任意の精度と大きな数の (正確で効率的な) 実装は面倒であり、製品コードで使用する場合は、テスト済みのフレームワーク (例: boost、gmpなど) を使用することをお勧めします。

ただし、自分で実装する場合は、数値をビットのシーケンスとしてではなくunsigned int、ハードウェア ALU 機能を最大限に活用するためのマシン ワードのシーケンスとして保存します。したがって、各ワードはすでにビット数を表しており、ALU はそれらを乗算する方法を知っています。

数値に数字を掛けるとn(基数は関係ありません)、数字を含む数値が得られることに注意してください2n。たとえば、99 * 99 = 9801 (基数 10)、0xFF * 0xFF = 0xFE01 (基数 16) のようになります。したがって、 がシステム上にある場合std::uintmax_tはstd::uint64_t、番号を のシーケンスとして保存できますstd::uint32_t。2 桁を掛ける場合は、2 桁に変換してstd::uint64_t掛けます。上位 32 ビットは、次の上位桁の乗算に使用される部分になります。(実際には、変数を直接乗算することもできますがstd::uintmax_t、結果の上位部分を取得することは、通常、少しトリッキーであり、対応するEDX\RDXレジスタにアクセスするためにインライン アセンブリが必要です。)

この知識があれば、学校の乗算方法の実装は簡単です。数値のすべての桁を反復し、すべての桁a[i]を数値aで乗算するだけbです (キャリーを伝播することを忘れないでください)。i結果を桁単位でシフトし、すべてを最終結果に追加します。

このアルゴリズムは、プリミティブ乗算の数に関して二次的な複雑さを持っていることに注意してください。数が (非常に) 大きい場合は、カラツバや FFT や Schönhage-Strassen などのより洗練された方法に切り替えることもできます。ただし、この場合は、代わりにライブラリを使用することを強くお勧めします。

于 2013-04-08T13:53:34.160 に答える