先日、桁上がりについて質問させていただいた者です。
加算と減算はなんとか完成したのですが、乗算と除算になって混乱してしまいました。
二進数の乗算、除算はビットシフトと関係がありますが、私の作っているものの場合はどのようなソースコードにすればよいでしょうか?
(ちなみに、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ベストアンサー
- 回答日時:
★アドバイス
>加算と減算はなんとか完成したのですが、乗算と除算になって混乱してしまいました。
↑
何が混乱したのでしょうか?
>二進数の乗算、除算はビットシフトと関係がありますが、
>私の作っているものの場合はどのようなソースコードにすればよいでしょうか?
↑
まずはビットシフトで乗算を作ってみましょう。
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
- 回答日時:
★回答者 No.6 です。
修正です。・最後の部分でキャストすればよいとアドバイスしましたが一部、間違いました。
間違い⇒ #define LONGMASK ((LONGINT1)(~((~0UL) << LONGBITS)))
正しい⇒ #define LONGMASK ((LONGINT2)(~((~0UL) << LONGBITS)))
※LONGINT1 を LONGINT2 にして下さい。
・以上です。
No.6
- 回答日時:
★そうでしたか。
>私は自分で学習したところ(まだ初めて2ヶ月くらいですが)までの内容でどこまでできるかという挑戦で
>作り始めたので、この形で完成させてみたいと思っています。
↑
薄々は感じてはいましたけど。
ソース上で二進数の形に変換するとき 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
- 回答日時:
ANo.2 です。
>アドバイスいただいたような内容はまだ私にとっては難しすぎるんです。
確かに、Oh-Orangeさんの解説は(私としても)非常に参考になります。
ただ理解できないと残念になってしまうので便乗して
Oh-Orangeさんに、ある1行でお聞きしたいのですが…、
#define LONGMASK (~((~0UL) << LONGBITS))
とは、
符号なし(UNSIGNED LONG)のコンパイル上でのnビット
(例えば通例32ビット)で
→00000000000000000000000000000000
を1補数反転
→11111111111111111111111111111111
のLONGBITS=8ビット上位シフト
→11111111111111111111111100000000
の1補数反転
→00000000000000000000000011111111
で当確する桁数ビットマスクを得る
と言う、解釈でよいのでしょうか?
(すみません、どさくさまぎれで…)
No.4
- 回答日時:
そもそも,あなたがやってるのは2進数の計算ではありませんが..
scanf(..., &x)...scanf(..., &y)
z=x*y;
とやれば,これがすでに2進数での計算が行われています.現代のコンピュータは全部二進演算するように作られているのですから.
整数配列の各要素に1か0だけ入れて,2進数の筆算をなぞるような形で演算するというのは,効率が悪いだけで意味がありません.
何がやりたいのでしょうか?
単に頭の体操がしたいだけでしょうか?
No.3
- 回答日時:
★回答者 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() の定義は書き換える必要はありません。
※そのための記号的数、型の再定義を行っているのですから。
・以上。
この回答への補足
申し訳ありません。私はほとんど初心者なので、情けないのですが、アドバイスいただいたような内容はまだ私にとっては難しすぎるんです。
私は自分で学習したところ(まだ初めて2ヶ月くらいですが)までの内容でどこまでできるかという挑戦で作り始めたので、この形で完成させてみたいと思っています。
>2 のべき乗以外も掛け算できるように最終的にはするつもりなのでしょうか?
>この一塊を 8 個の配列にセットして扱っていますが、これには何か
意図があるのでしょうか?
↑
2のべき乗以外で掛け算できるようにはしようとは思っていません。
上に書いたように初心者ですので、恥ずかしながら今のところは簡単にしようと思っています。一塊を 8 個の配列にセットして扱っているのは、そういう方法しか思いつかなかったので、そうしただけであって、特に意図はありません。
せっかく回答をいただいたのに自分勝手のことを言って申し訳ないです。
No.2
- 回答日時:
実際の処理はこんな感じかと思います。
#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は2のべき乗の値とする)");
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);
}
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# c言語でユーザ関数を利用して複素数のべき乗と絶対値の数列を計算するプログラムが作りたいです。 3 2023/01/29 22:13
- C言語・C++・C# C言語 プログラミング 4 2022/05/22 11:53
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# 至急教えてください。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分 1 2022/07/19 17:03
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
- C言語・C++・C# 至急教えてください!プログラミングの問題です。 割られる整数と割る整数を受け取って、商と余りを出力す 3 2022/07/05 10:23
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# 宣言する関数の形が決まっている状態で、 str1とstr2の文字列をこの順に引っ付けてstrに保存し 2 2022/05/30 18:21
- C言語・C++・C# 至急お願いします。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分母 3 2022/07/19 17:09
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
【C言語教えてください】sin波...
-
C言語についてです。 アスタリ...
-
C言語で四則演算を使って10を作...
-
分数を表示するプログラム(長...
-
C言語です このプログラミング...
-
strcmp
-
空白表示
-
改行について 1行に何個かづ...
-
2から120以下の素数を求める
-
カレンダー作成
-
縦の棒グラフ
-
C言語【おみくじプログラム】
-
hit&bolwのプログラミングがで...
-
ソースコードの確認をお願いし...
-
C言語で四則演算を使って結果が...
-
多項式のユークリッドの互除法...
-
位数を求めるプログラム
-
構造体配列をきれいに表示するには
-
台形の面積を求めるプログラム
-
C言語 素数判定
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
10個出力で改行したいのですが...
-
既約分数の表示プログラム
-
printf で二進表示を行いたい。
-
8人分のテストの点数を入力し、...
-
printf( " %2d", p * q );
-
strcmp
-
CTRL+Dでループを抜けるには
-
4の倍数を論理演算で表す。。
-
%P と %X の違い
-
【C言語教えてください】sin波...
-
c言語でAからZまでを表示する...
-
cshの文字列操作(0埋め)
-
万年カレンダーのC言語プログラ...
-
コマンドラインに出力した文字...
-
scanfに文字が入力されたときに...
-
ホームページをC言語で作りたい...
-
改行について 1行に何個かづ...
-
コンパイルエラーについて
-
台形の面積を求めるプログラム
-
なぜgccはstdio.hをインクルー...
おすすめ情報