2進数の1の数を数える問題

質問

次の問題に対して、以下のソースを考案し、実行したところ、以下のようになりました。

【問】
◆◆◆◆◆
　与えられた10進数の整数Nを2進数に変換したときの1の個数を答えよ。
　整数の10進数を2進数に変換するには、変換したい10進数を商が0になるまで2で割り続け、求めた余りの部分を逆順に並べる。
例)
13が入力として与えられた場合、以下のように2で割り続け2進数を求める。
13 / 2 = 6 ・・・余り 1
6 / 2 = 3 ・・・余り 0
3 / 2 = 1 ・・・余り 1
1 / 2 = 0 ・・・余り 1
　求められたそれぞれの余りを逆順に並べたものが2進数への変換結果となる。
　よって入力が13ならば2進数への変換結果は
1101
になり、1は3個あるので出力は3になる。
[入力例1]
13
[出力例1]
3
[入力例2]
45
[出力例2]
4
◆◆◆◆◆

（自分の解答、□はタブ）
◆◆◆◆◆
#include <stdio.h>
#include <stdlib.h> /* EXIT_SUCCESS */

int main(void)
{
□int n, bit, s;
□scanf("%d", &n);
□
□bit = n % 2;
□n /= 2;
□s = 0;
□while(n) {
□□if (bit)
□□□s++;
□bit = n % 2;
□n /= 2;
□}
□printf("%d", s);
□return EXIT_SUCCESS;
}
◆◆◆◆◆

（実行結果1）
◆◆◆◆◆
[入力]
13
[出力]
2
◆◆◆◆◆

（実行結果2）
◆◆◆◆◆
[入力]
45
[出力]
3
◆◆◆◆◆

となり、正解となりません。
　自分の考えとしては、入力された数値を変数nに収め、これをどんどん2で割っていき、そのときの余り(0か1)を変数bitに収めていき、nが0になるまで処理を繰り返し、bitが0でないとき、変数s(初期値0)に1ずつ加算していき、最後にsを出力する、という方針です。
　初期値の設定辺りが間違っているのだと思いますが、これ以上いくら考えても正解が得られません。どこがどう間違っているのでしょうか。どなたかご教授頂きたく、お願い致します。

回答No.2

maiko0318 · ベストアンサー

惜しい。これが正解。

#include <stdio.h>
#include <stdlib.h> /* EXIT_SUCCESS */

int main(void)
{
□int n, bit, s;
□scanf("%d", &n);
□
□s = 0;
□while(n) {

□□printf("%d/2=%d・・・余り%d\n",n,n/2,n%2);
□□bit = n % 2;
□□n /= 2;

□□if (bit)
□□□s++;

□}
□printf("%d", s);
□return EXIT_SUCCESS;
}

ヒントとして途中経過を表示しているから考えてみてください。

回答No.4

Ogre7077

ループ処理に失敗していますね
同様の処理を二箇所に分けているのも感心しません。

あと最近のコンパイラなら自動的に最適化してくれますが、
二進数の処理をするなら、やはりビット演算で書くのが筋でしょう。

// 正解例 ただし入力値が正の整数の場合のみ
int s, b;
for (s = 0, b = 入力値; b != 0; b >>= 1) {
□ if(b & 1 > 0) s++;
}
printf("%d is %d\n", 入力値, s);

--
出題の例からは外れますが、別解として

// K&R に登場する高速化した処理
int s, b;
for (s = 0, b = 入力値; b != 0; s++) {
□ b &= b - 1;
}
printf("%d is %d\n", 入力値, s);

// 分割統治法を用いた実用的な処理
unsigned int t = 入力値;
t -= (t >> 1) & 0x55555555;
t = (t & 0x33333333) + ((t >> 2) & 0x33333333);
t = (t + (t >> 4)) & 0x0f0f0f0f;
t += t >> 8;
t += t >> 16;
t &= 0x3f;
printf("%d is %d\n", 入力値, t);

回答No.3

LunaSun

みんな、do～whileを忘れないであげてね。

#include <stdio.h>
#include <stdlib.h> /* EXIT_SUCCESS */

int main(void)
{
□int n, bit, s;
□scanf("%d", &n);

□s = 0;
□do {
□□s += n % 2;
□} while ((n /= 2));

□printf("%d\n", s);
□return EXIT_SUCCESS;
}

回答No.1

dolittle0

while ループの後に、if(bit) s++; を追加すればいいと思います。

お礼

ありがとうございます。