質問: 2進数の乗算と除算 先日、桁上がりについて質問させていただいた者です。 加算と減算はなんとか完成したのですが、乗算と除算になって混乱してしまいました。 二進数の乗算、除算はビットシフトと関係がありますが、私の作っているものの場合はどのようなソースコードにすればよいでしょうか? (ちなみに、bの値は2のべき乗に限定しています。) int main(void) { int a,b,i; int x[8],y[8]; puts("二つの符号なし整数を入力してください。(ただしa>bとし、bは2のべき乗の値とする)"); printf("a="); scanf("%d",&a); printf("b="); scanf("%d",&b); printf("\n"); /*二進数の形に変換*/ for(i=0;i<=7;i++){ x[i]=a%2; a=a/2; y[i]=b%2; b=b/2; } puts("aとbをそれぞれ二進数で表すと"); printf("a="); for(i=7;i>=0;i--){ printf("%d",x[i]); } puts(""); printf("b="); for(i=7;i>=0;i--){ printf("%d",y[i]); } printf("となります。\n\n"); return(0); }
回答: ★回答者 no.1 です。 >私はビットシフトのことが完全に把握できていなかったので混乱してしまっていたんです。 >なので、アドバイス通りにまずは乗算からじっくり理解したいと思います。 ↑ それならもう少し演算についてアドバイスします。 まず最初に乗算する b の数はなぜ 2 のべき乗でないといけないのですか? お聞きしたいです。もし、プログラミングを簡単に行うために限定しているのなら 2 のべき乗以外も掛け算できるように最終的にはするつもりなのでしょうか? この辺はどう考えているのですか。 ・あとちょっと気になったのですが 8 ビットを1つの塊として加算、減算、乗算、除算を 実装していますよね。この一塊を 8 個の配列にセットして扱っていますが、これには何か 意図があるのでしょうか? ・普通なら unsigned char 型で 8 ビットを管理して演算するときは 2 倍の unsigned short 型 などで処理します。その後、8 ビットの配列× n 個に格納するようにします。 こういうのは俗に『多倍長演算』という考えです。 ・例えば『多倍長演算』という考えでの加算は下のサンプルのようになります。 サンプル: // 記号定数 #define longbits (8) // 一度に扱うビット数 #define longmask (~((~0ul) << longbits)) // 一度に扱うビットマスクデータ(0xff) // 型の再定義 typedef unsigned char longint1; // 基本のデータ型 typedef unsigned short longint2; // 基本のデータの倍の型 // 8 ビットを一塊とした n 個分の配列加算 int add( longint ans[], longint a[], longint b[], int max ) { longint2 carry = 0; int i; for ( i = 0 ; i < max ; i++ ){ if ( (carry = (carry + a[i] + b[i])) > longmask ){ ans[ i ] = (longint1)(carry & longmask); carry = 1; } else{ carry = 0; } } return (carry ? 1 : 0); // オーバーフローしたら 1 を返す } 説明: ・上記のサンプルは 8 ビットを1つの塊として max 個分の配列を加算する関数です。 8 ビットの加算では longint1 a[1], longint1 b[1], longint1 ans[1]; と宣言して add( ans, a, b, 1 ); として呼び出します。 64 ビットの加算では longint1 a[8], longint1 b[8], longint1 ans[8]; と宣言して add( ans, a, b, 8 ); として呼び出します。 800 ビットの加算では longint1 a[100], longint1 b[100], longint1 ans[100]; と宣言して add( ans, a, b, 100 ); として呼び出します。 ※いずれも戻り値はオーバーフローすれば 1 を返す事になります。 ※800 ビットの場合は 2 の 800 乗(0~6.668e+240)までの計算が行えます。 ・上記のサンプルを参考にすれば『多倍長整数演算』として何桁でも演算可能になります。 また、同じような考えで sub(減算)、mul(乗算)、div(除算)、shl(左シフト)、shr(右シフト) の関数を作成して『多倍長整数演算ライブラリ』として用意するのも良いでしょう。 最後に: ・上記のサンプルでは 8 ビットを一塊として処理していますが、実際にはもっと多い 16、32 ビット を一塊の単位として処理した方が計算速度が速くなります。また、i カウンタを用いずにポインタ を使えばさらに早く演算できるようになります。増やすときは次のようにします。 ●16 ビットの場合 // 記号定数 #define longbits (16) // 一度に扱うビット数 #define longmask (~((~0ul) << longbits)) // 一度に扱うビットマスクデータ(0xff) // 型の再定義 typedef unsigned short longint1; // 基本のデータ型 typedef unsigned long longint2; // 基本のデータの倍の型 ●32 ビットの場合 // 記号定数 #define longbits (32) // 一度に扱うビット数 #define longmask (~((~0ull) << longbits)) // 一度に扱うビットマスクデータ(0xff) // 型の再定義 typedef unsigned long longint1; // 基本のデータ型 typedef unsigned long long longint2; // 基本のデータの倍の型 ↑ c99 規格に対応した long long 型が使えることが前提です。 未対応のコンパイラでは 32 ビットで使います。 ※ビット数を 16、32 に変更しても関数 add() の定義は書き換える必要はありません。 ※そのための記号的数、型の再定義を行っているのですから。 ・以上。