2進数の乗算と除算

質問

先日、桁上がりについて質問させていただいた者です。
加算と減算はなんとか完成したのですが、乗算と除算になって混乱してしまいました。
二進数の乗算、除算はビットシフトと関係がありますが、私の作っているものの場合はどのようなソースコードにすればよいでしょうか？
(ちなみに、bの値は２のべき乗に限定しています。)

int main(void)
{
int a,b,i;
int x[8],y[8];

puts("二つの符号なし整数を入力してください。(ただしa>bとし、bは２のべき乗の値とする)");
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

Oh-Orange · ベストアンサー

★アドバイス
＞加算と減算はなんとか完成したのですが、乗算と除算になって混乱してしまいました。
　↑
　何が混乱したのでしょうか？
＞二進数の乗算、除算はビットシフトと関係がありますが、
＞私の作っているものの場合はどのようなソースコードにすればよいでしょうか？
　↑
　まずはビットシフトで乗算を作ってみましょう。
　2進数の乗算は次のようになります。(2のべき乗限定)
　例えば
　a…123
　b…32(2の5乗)
　この場合は 123 を 2 進数に変換して 01111011 とします。
　その後に 01111011 を左に 5 ビットシフトすればよいだけです。
　なお、シフトさせた結果の配列サイズは x[8] の倍 16 必要になります。
　下にそのサンプルを載せておきます。

サンプル:
int x[ 8 ] = { 1, 1, 0, 1, 1, 1, 1, 0 };　←10進数で 123 を表す
int y[ 8 ] = { 0, 0, 0, 0, 0, 1, 0, 0 };　←10進数で 32 を表す
int z[ 16 ];　←シフトした結果を格納
int shift;　←シフトするビット数

// シフト数を算出
for ( shift = i = 0; i < 8 ; i++ ){
　if ( y[i] == 1 ){
　　shift = i;
　　break;
　}
}
// 初期化
for ( i = 0 ; i < 16 ; i++ ){　←z[16]の回数
　z[ i ] = 0;
}
// 左シフト
for ( i = 0 ; i < 8 ; i++ ){　←x[8]の回数
　z[ i + shift ] = x[ i ];
}
// z = x * y の表示
printf( "z=" );
for ( i = 15 ; i >= 0 ; i-- ){
　printf( "%d", z[i] );
}
printf( "\n" );

説明:
・上記のサンプルをつければ b が 2 のべき乗限定で乗算らしきものが出来ます。
　前回の加算は 8 ビットでしたよね。すると乗算も除算も 8 ビットという事ですよね。
　乗算も除算も演算は倍の 16 ビット分のサイズが必要になります。ここ注意！
・あと上記のサンプルの x, y に直接 2 進値を入れていますが x[0]、y[0] が下位ビット
　になります。これは質問者さんの仕様に合わせています。

その他:
・ちゃんとした乗算(2のべき乗限定ではないタイプ)を行いたい場合は次のようになります。
　a=123
　b=12
　の場合は
　a=01111011
　b=00001100
　となるので b の下位ビットから順番にスキャンして 0 ならそのまま、1 なら a を自分の
　ビット数だけ左シフトすれば良い。この結果を倍の 16 ビット配列に加算していけばやがて
　b のすべてのビットを処理したとき a と b の乗算結果になります。
・除算は別の機会にアドバイスします。まずは乗算を作ってみて下さい。
・以上。

お礼

回答ありがとうございます！私はビットシフトのことが完全に把握できていなかったので混乱してしまっていたんです。
なので、アドバイス通りにまずは乗算からじっくり理解したいと思います。

回答No.7

Oh-Orange

★回答者 No.6 です。修正です。
・最後の部分でキャストすればよいとアドバイスしましたが一部、間違いました。
　間違い⇒　#define LONGMASK　((LONGINT1)(~((~0UL) << LONGBITS)))
　正しい⇒　#define LONGMASK　((LONGINT2)(~((~0UL) << LONGBITS)))
　※LONGINT1 を LONGINT2 にして下さい。
・以上です。

回答No.6

Oh-Orange

★そうでしたか。
＞私は自分で学習したところ(まだ初めて２ヶ月くらいですが)までの内容でどこまでできるかという挑戦で
＞作り始めたので、この形で完成させてみたいと思っています。
　↑
　薄々は感じてはいましたけど。
　ソース上で二進数の形に変換するとき 2 で割ったあまりを x[i] にセットして a = a/2; を
　行っていますね。私ならビット演算で AND、右シフトしてセットします。
　つまり、
　/*二進数の形に変換*/
　for ( i = 0 ; i < 8 ; i++ ){　←ここは 8 にする(8Bitなので分かりやすく)
　　x[ i ] = a & 0x1;　←2 で割ったあまり 0、1 がセットされる
　　y[ i ] = b & 0x1;
　　a >>= 1;　←2 で割ったのと同じ効果になる
　　b >>= 1;
　}
　↑
　こんな感じです。
　でも多分、ビット演算はまだ知らないのでしょうね。
　下の『参考URL』をどうぞ。

＞2のべき乗以外で掛け算できるようにはしようとは思っていません。
＞上に書いたように初心者ですので、恥ずかしながら今のところは簡単にしようと思っています。
　↑
　やっぱりプログラミングを簡単に行うために限定していたのですね。
　でもこれをきっかけに 2 のべき乗以外でも掛け算できるように考えてみてはどう。
　もし出来たらスキルアップしますよ。
＞一塊を 8 個の配列にセットして扱っているのは、そういう方法しか思いつかなかったので、
＞そうしただけであって、特に意図はありません。
　↑
　これは質問者さんの仕様という事ですね。
　分かりました。
　でも、回答者 No.4 さんの言うとおりで変数はコンピュータ上で全部 2 進数で格納されています。
　なので x * y とすれば 2 進数の演算を行ったことにもなるのです。
　でも 2 進数の演算を理解するという目的では今回の質問はそれなりに意味があります。
　理由は今回の方式で四則演算が出来ればその後に『多倍長演算』の考えに繋がりますので。

●質問者さんとVTClient さんへ。
＞で当確する桁数ビットマスクを得る
＞と言う、解釈でよいのでしょうか？
　↑
　そうですね。解釈は正しいです。
・add() 関数で 8 ビットの最大値 0xFF を定義すればよいのですが、LONGBITS だけを
　可変すれば自動的に作成してくれるようにしたためです。これなら 7、15、20 ビットでも
　自分で 0x7F、0x7FFF、0xFFFFF としなくても良いからです。
・あとちょっと修正しますと
　#define LONGMASK　(~((~0UL) << LONGBITS))
　の行は
　#define LONGMASK　((LONGINT1)(~((~0UL) << LONGBITS)))
　とキャストした方がコンパイルで警告メッセージが出ませんね。
　参考にする際はキャストした方がいいです。
・以上。

参考URL：

http://www9.plala.or.jp/sgwr-t/c/sec14.html

お礼

回答ありがとうございます！それと、私のわがままをご理解いただきましてありがとうございます。
参考URLのおかげでビット演算が少しずつわかってきました。
これからもっと深くじっくりと理解したいと思います。

回答No.5

noname#50176

ANo.2 です。
＞アドバイスいただいたような内容はまだ私にとっては難しすぎるんです。

確かに、Oh-Orangeさんの解説は（私としても）非常に参考になります。
ただ理解できないと残念になってしまうので便乗して
Oh-Orangeさんに、ある1行でお聞きしたいのですが…、

#define LONGMASK　(~((~0UL) << LONGBITS))
とは、

符号なし（UNSIGNED LONG)のコンパイル上でのｎビット
（例えば通例32ビット）で
→00000000000000000000000000000000
を1補数反転
→11111111111111111111111111111111
のLONGBITS=8ビット上位シフト
→11111111111111111111111100000000
の1補数反転
→00000000000000000000000011111111

で当確する桁数ビットマスクを得る

と言う、解釈でよいのでしょうか？
（すみません、どさくさまぎれで…）

回答No.4

a-saitoh

そもそも，あなたがやってるのは2進数の計算ではありませんが．．
scanf(..., &x)...scanf(..., &y)

z=x*y;
とやれば，これがすでに2進数での計算が行われています．現代のコンピュータは全部二進演算するように作られているのですから．

整数配列の各要素に1か0だけ入れて，2進数の筆算をなぞるような形で演算するというのは，効率が悪いだけで意味がありません．

何がやりたいのでしょうか？

単に頭の体操がしたいだけでしょうか?

回答No.3

Oh-Orange

★回答者 No.1 です。
＞私はビットシフトのことが完全に把握できていなかったので混乱してしまっていたんです。
＞なので、アドバイス通りにまずは乗算からじっくり理解したいと思います。
　↑
　それならもう少し演算についてアドバイスします。
　まず最初に乗算する b の数はなぜ 2 のべき乗でないといけないのですか？
　お聞きしたいです。もし、プログラミングを簡単に行うために限定しているのなら
　2 のべき乗以外も掛け算できるように最終的にはするつもりなのでしょうか？
　この辺はどう考えているのですか。
・あとちょっと気になったのですが 8 ビットを１つの塊として加算、減算、乗算、除算を
　実装していますよね。この一塊を 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 ビットを１つの塊として 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() の定義は書き換える必要はありません。
　※そのための記号的数、型の再定義を行っているのですから。
・以上。

補足

申し訳ありません。私はほとんど初心者なので、情けないのですが、アドバイスいただいたような内容はまだ私にとっては難しすぎるんです。
私は自分で学習したところ(まだ初めて２ヶ月くらいですが)までの内容でどこまでできるかという挑戦で作り始めたので、この形で完成させてみたいと思っています。

＞2 のべき乗以外も掛け算できるように最終的にはするつもりなのでしょうか？
＞この一塊を 8 個の配列にセットして扱っていますが、これには何か
　意図があるのでしょうか？
↑
2のべき乗以外で掛け算できるようにはしようとは思っていません。
上に書いたように初心者ですので、恥ずかしながら今のところは簡単にしようと思っています。一塊を 8 個の配列にセットして扱っているのは、そういう方法しか思いつかなかったので、そうしただけであって、特に意図はありません。

せっかく回答をいただいたのに自分勝手のことを言って申し訳ないです。

回答No.2

noname#50176

実際の処理はこんな感じかと思います。

#include <stdio.h>

int nishin(int h[],int size,int a)
{
/*二進数の形に変換*/
for(int i=0;i<size;i++){
h[i]=a%2;
a=a/2;
}
return 0;
}

int main(void)
{
int x[16],y[16],a,b,i,j,m,n,p,w,z;
unsigned int size_8=8,size_16=16;
puts("二つの符号なし整数を入力してください。(ただしa>bとし、bは２のべき乗の値とする)");
do{
printf("a=");scanf("%d",&a);
printf("b=");scanf("%d",&b);
printf("\n");
if (!(a&&b)) return 0;
for(i=0x80,j=0;i;i>>=1) j+=b&i?1:0;
}while(a<=b||(a|b)>0x100||a<0||b<0||j-1);
// 入力条件を満たせば続きます

puts("aとbをそれぞれ二進数で表すと");
printf("a=");
nishin(x,size_8,a);
for(i=size_8-1;i>=0;i--){
printf("%d",x[i]);
}
puts("");
printf("b=");
nishin(y,size_8,b);
for(i=size_8-1;i>=0;i--){
printf("%d",y[i]);
}
printf("\r\n");

for(j=0,m=a,n=b;j<8;j++,n>>=1) m=n&1?m<<j:m;
printf("a*b=");//掛け算
nishin(x,size_16,m);
for(i=size_16-1;i>=0;i--){
printf("%d",x[i]);
}
printf("\r\n");
for(j=0,p=m=a,n=b,z=0,w=0;j<8;j++,n>>=1,p>>=1)
{
m=n&1?m>>j:m;
if (!(n&1) && !w) z|=(p&1)<<j,w=n>>1&1;
}
printf("a/b=");//割り算
nishin(x,size_16,m);
for(i=size_16-1;i>=0;i--){
printf("%d",x[i]);
}
printf("\r\n");
printf("a mod b=");//余り
nishin(y,size_16,z);
for(i=size_16-1;i>=0;i--){
printf("%d",y[i]);
}
printf("\r\n");

printf("\r\nとなります。\n\n");
return(0);
}

お礼

回答ありがとうございます！とても参考になりました。