C 入力値が大きくなったとき動作しない

Question

入力された2つの数字の間にある数字の中で2進数変換してひっくり返したとき、変換する前と変わらないものの個数を求めるプログラムを組んだのですが、入力値が大きくなると正しい答えが出ません。
具体的には1000,5000と入力すると1が出てきたりするのですがどうすればいいのでしょうか。

#include<stdio.h>
int main(void){
	int x,y,z;
	int a,b,c;
	int d,e,count=0;
	
	scanf("%d,%d",&x,&y);
	for(z=x+1;z<y;z++){
		if(z%2!=0){
			a=z;
			b=0;
			c=1;
			while(a>0){
				b=b+(a%2)*c;
				a=a/2;
				c=c*10;
			}
			d=b;
			e=0;
			while(d>0){
				e=e*10+d%10;
				d=d/10;
			}
		if(b==e) count++;
		}
	}
	printf("%d",count);
}

Answer 1

こんにちは。

お使いのコンパイラにもよりますが、オーバーフローしていると思います。
例えば、zに4096が入っている時を考えます。
これは、2進数で表記すると、0001 0000 0000 0000となります。（Windowsの電卓でプログラマ・モードを使うと簡単に表示できますよ。)

suzariaさんは、これを変換してbへ入れていますが、その時、10進数で表現した時にまるで2進数であるかのように見えるよう変換されてます。(10進数の各桁が0 or 1となる。) なかなか工夫されてますね。

さて、z=4096の時、10進数で表現するとb=1,000,000,000,000となっています。
このbを再度2進数で表現すると、1110 1000 1101 0100 1010 0101 0001 000 000 000となり、全部で40ビット必要とします。
int型は32ビットしか記録できないコンパイラが多いですので、オーバーフローしている筈です。

---

C言語は2進数表現をサポートしていませんので、直接2進数で表現しようとするとなかなか面倒です。
学習が目的であれば、2進数を文字列で表現するようなプログラムにすると捗ると思います。
%sで表示できますのでデバッグしやすいですし、結果をstrcmp()で比較できます。もちろん、オーバーフローすることもないです。
文字列領域のバイト数はint型のビット数+1バイトの固定長でできると思います。

Comments

[suzaria]

オーバーフローにも気を付けないといけないのですね...
ありがとうございました！

Answer 2

期待通りの結果にならない原因はChironian さんのご指摘通り、オーバーフローによるものです。

2進数を少し誤解されているようです。int型変数の値は元々2進数で記憶されているので、変換の必要はありません。「2進数表記」で表示させたいということであれば、数値を文字列に変換する、という作業が必要になりますが、ご質問の要件ではその必要はないように思います。

つまり、「2進数変換」は不要で、「ビットの上位と下位をひっくり返す変換」をすれば良いのです。

元の値の最下位ビットを%2で取り出して2で割り、変換先の値は2倍して先ほど取り出した値を足す。これをintのビット数(32)回繰り返せば、ビットをひっくり返すことができます。
ビットをひっくり返した値が作れたら、後はそれを元の値と単純に比較するだけです。

Comments

[suzaria]

2進数にしない方法、とてもシンプルで無事計算することができるようになりました。
わかりやすい説明ありがとうございました！

Answer 3

すでに回答があるように、オーバーフローしているのが原因とおもいます。
プログラム中では、 数字 15 を 1111(１０進) に変換しています。
そのため例えば 4095 は内部では 111111111111 の10進を作ろうとしていて、int の最大数を超えてしまいます。
この 2 進表記見えるような 10 進数への変換をしないコードを書いてみました。

#include<stdio.h>
// See http://www.harukitchen.com/program/binary.c
//  2進表記の文字列をつくる
void binary(char *b, int d)
{
	int i = 0, j = 0, tmp;
	if (d < 0) return;
	do {
		b[i++] = d % 2 + '0';
	} while(d >>= 1);
	i--;

	/* reverse */
	while (i > j) {
		tmp = b[j];
		b[j] = b[i];
		b[i] = tmp;
		j++; i--;
	}

	b[i + j + 1] = '\0';
	return;
}

int main(void) {
  int x, y, z, z1;
  int work;
  int count = 0;

  scanf("%d,%d", &x, &y);
  for (z = x + 1; z < y; z++) {
    if (z % 2 != 0) {
      work = z;
      z1 = 0;
      while (work != 0) {
        z1 = z1 * 2 + work % 2;
        work /= 2;
      }
      if (z == z1) {
        count++;
        char buf[1000];
        binary(buf, z);
        printf("%d (%s)\n", z, buf);
      }
    }
  }
  printf("%d\n",count);
}

実行例

katoy-MacBook-Pro:tmp katoy$ gcc 1.c

katoy-MacBook-Pro:tmp katoy$ ./a.out
0,17
1 (1)
3 (11)
5 (101)
7 (111)
9 (1001)
15 (1111)
6

$ ./a.out
4500,5000
4529 (1000110110001)
4593 (1000111110001)
4617 (1001000001001)
4681 (1001001001001)
4777 (1001010101001)
4841 (1001011101001)
4889 (1001100011001)
4953 (1001101011001)
8

Comments

[suzaria]

とてもわかりやすいです！
わざわざプログラムを組んでくださり本当にありがとうございました！
参考にさせていただきます。