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

質問

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

#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);
}

回答No.1

maku_x · ベストアンサー

桁上がり変数 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進数表示すれば同じ結果が得られますが、これではいけませんか。

お礼

回答ありがとうございます。
おかげで、桁上がりが理解できました！

回答No.7

Mr_tenten

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

回答No.6

Mr_tenten

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

６行で記述すると次のようになります

　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をわざわざ用意したのは配列の参照回数を減らし、少しでも速度を向上するためですｗ

％や/演算子を省いたものを使用したいならば、他の方の回答を参考にしてください。力不足で申し訳ないです。

お礼

回答ありがとうございます。力不足だなんてとんでもない、とても役に立ちました。

回答No.5

Oh-Orange

★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( "<加算>\n" );
printf( "c=a+b=" );
printf( "%d ", carry );　←桁上がりも表示
for ( i = 7 ; i >= 0 ; i-- ){
　printf( "%d", z[i] );
}
printf( "\n" );

その他:
・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;　←最終的な桁上がりをセット
　↑
　こんな感じでも良いかな。
・以上。

お礼

回答していただいてありがとうございます！
こういう考え方は思いつかなかったので、試してみます。

回答No.4

fatbowler

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

お礼

回答ありがとうございます！そうですね、まずは基本的なことから手計算でやり直してみます。

回答No.3

rnknsk

８桁までだとすると９桁目がないのでオーバーフローという状態になります。
日本語だと桁あふれだったかな。

加算したときの合計が２５５を超えなければ８桁のままで問題ないと思います。
ただマイナスとか入れたりしたら一番左側がプラスかマイナスかに
つかわれちゃうのでそこまで考えてみるのもいいんじゃないかと。

お礼

回答ありがとうございます。非常に役に立ちました。

回答No.2

asuncion

a > bという制約条件を設ける必要はないと思います。今は1 + 1の計算もできない状態です。
それよりはむしろ、aとbを二進法で表現したときのビット数が最大8という条件が
ありますので、0 <= a <= 255（bも同じ）という条件を付けるべきでしょう。

足し算の結果は9ビットになる場合があります。z[8]では足りません。

右側の桁から足し算を行なうのはよいですが、^ 演算子はさすがにまずいですね。
ある桁どうしを普通に足し算して、1+1=2のときにどうすればよいかを
考えてみてください。

お礼

回答ありがとうございます。
言われてみると、おっしゃる通りかもしれません。
いろいろ、試してみたいと思います。