2進数の加算の繰り上がり

Question

２進数の四則演算のプログラムを作りたいと思い、２進数を表示するところまではできたのですが、加算になると繰り上がりという壁にぶつかってしまいました。繰り上がりや桁上げなどがよく分からないので、お教えください。(下のソースコードが繰り上がりのない加算をするまでのものです)

#include <stdio.h>

int main(void)
{
int a,b,i,j,x[8],y[8],z[8];
do{
puts("二つの符号なし整数を入力してください。(ただしa>bとし、bはのべき乗の値とする)");
printf("a="); scanf("%d",&a);
printf("b="); scanf("%d",&b);

if(a　<　=　b)
puts("入力した値がa>bになっていません。\a");
}while(a　<　=　b);

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");

printf("<加算>\n");
printf("c=a+b=");

for(　j　=　7;　j　>　=　0;　j　-　-){
z[j]=x[j]^y[j];
printf("%d",z[j]);
}
return(0);
}

maku_x · Accepted Answer

桁上がり変数 carry を使って、

:
(前略)
:
main(void)
{
int a,b,i,j,x[8],y[8],z[8], carry=0;
:
(中略)
:
for(j=0; j<8; j++) {
z[j]=x[j]^y[j]^carry;
carry = (x[j] & y[j]) | (x[j] & carry) | (y[j] & carry);
}

if (carry != 0) printf("%d", carry);
for(j=7; j>=0; j--) {
printf("%d",z[j]);
}
:
(後略)
:

とすれば良いのではないでしょうか。

※ (a + b) を 2進数表示すれば同じ結果が得られますが、これではいけませんか。

asuncion · Answer

a > bという制約条件を設ける必要はないと思います。今は1 + 1の計算もできない状態です。
それよりはむしろ、aとbを二進法で表現したときのビット数が最大8という条件が
ありますので、0 <= a <= 255（bも同じ）という条件を付けるべきでしょう。

足し算の結果は9ビットになる場合があります。z[8]では足りません。

右側の桁から足し算を行なうのはよいですが、^ 演算子はさすがにまずいですね。
ある桁どうしを普通に足し算して、1+1=2のときにどうすればよいかを
考えてみてください。

rnknsk · Answer

８桁までだとすると９桁目がないのでオーバーフローという状態になります。
日本語だと桁あふれだったかな。

加算したときの合計が２５５を超えなければ８桁のままで問題ないと思います。
ただマイナスとか入れたりしたら一番左側がプラスかマイナスかに
つかわれちゃうのでそこまで考えてみるのもいいんじゃないかと。

fatbowler · Answer

仕様がまだはっきり固まってないようです。
オーバーフローの処理をどうするか、マイナスの数をどうするか、
マイナスを許容する際には、１の補数か２の補数かなど。
繰り上がり、繰り下がりはプログラミングの問題ではなく、
手計算（筆算）でマスターしてください。

Oh-Orange · Answer

★2進数の加算のおさらい・0 ＋ 0 ＝ 0 　0 ＋ 1 ＝ 1 　1 ＋ 0 ＝ 1 　1 ＋ 1 ＝ 0　←ここで桁上がり　となりますよね。・という事は a=1、b=1 の時に carry ビットを 1 として用意すればよい。　そして carry ビットも a、b に足しこむようにすれば良い。　下にサンプルを載せます。なお、XOR を使っていません。サンプル: int carry;　←宣言に追加 // 計算 for ( carry = i = 0 ; i < 8 ; i++ ){　←下位ビットから計算　switch ( x[i] + y[i] + carry ){　←carry を足しこむ　　case 0:　z[ i ] = 0; carry = 0; break; 　　case 1:　z[ i ] = 1; carry = 0; break; 　　case 2:　z[ i ] = 0; carry = 1; break;　←桁上がり　　case 3:　z[ i ] = 1; carry = 1; break;　←桁上がり　　default: // エラー表示など　} } // 結果表示 printf( "<加算> " ); printf( "c=a+b=" ); printf( "%d ", carry );　←桁上がりも表示 for ( i = 7 ; i >= 0 ; i-- ){ 　printf( "%d", z[i] ); } printf( " " ); その他: ・z[] 配列は 9 にして z[8] に最終的な桁上がりが格納されるようにするのもいいかも。　つまり　int i, x[ 8 ], y[ 8 ], z[ 9 ];　←サイズを 9 に　　for ( z[1] = i = 0 ; i < 8 ; i++ ){　←下位ビットから計算　　switch ( x[i] + y[i] + z[i + 1] ){　←z[i+1] が carry です　　　case 0:　z[ i ] = 0; z[i + 1] = 0; break; 　　　case 1:　z[ i ] = 1; z[i + 1] = 0; break; 　　　case 2:　z[ i ] = 0; z[i + 1] = 1; break;　←桁上がり　　　case 3:　z[ i ] = 1; z[i + 1] = 1; break;　←桁上がり　　　default: // エラー表示など　　} 　} 　または　int i, carry, x[ 8 ], y[ 8 ], z[ 9 ];　←サイズを 9 に　　for ( carry = i = 0 ; i < 8 ; i++ ){ 　　if ( (z[i] = x[i] + y[i] + carry) >= 2 ){ 　　　z[ i ] -= 2;　// z[i] &= 1; でも良い。　　　carry = 0; 　　} 　　else{ 　　　carry = 1; 　　} 　} 　z[ i ] = carry;　←最終的な桁上がりをセット　↑ 　こんな感じでも良いかな。・以上。

Mr_tenten · Answer

***　はじめまして　***

６行で記述すると次のようになります

　int temp;　←追加
　for(i = 0,　ans[0] = 0;　i < 5;　i++){
　　temp = a[i] + b[i] + ans[i];
　　ans[i]　　　= temp % 2;
　　ans[i + 1]　= temp / 2;    
　}

一応分かりやすく書きましたが、ビットを表す配列が多大な場合、このプログラムは遅いです。
なぜなら、％演算子、/演算子は他の演算子に比べて非常に遅いためです。　tempをわざわざ用意したのは配列の参照回数を減らし、少しでも速度を向上するためですｗ

％や/演算子を省いたものを使用したいならば、他の方の回答を参考にしてください。力不足で申し訳ないです。

Mr_tenten · Answer

申し訳ありません。回答の修正です。
変数 i の範囲を８にして、ansをzの配列にし、zの配列を９つ用意してください。　自分で試したプログラムをそのまま写してしまいました。

2進数の加算の繰り上がり

桁上がり変数 carry を使って、

a > bという制約条件を設ける必要はないと思います。

８桁までだとすると９桁目がないのでオーバーフローという状態になります。

仕様がまだはっきり固まってないようです。

★2進数の加算のおさらい

*** はじめまして ***

申し訳ありません。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

*　はじめまして　*