ビット構成を表示するプログラム

Question

すいませんputcharｘ＞＞iではなく1になっていたのが原因でした。
putchar(((x>>i)&1U)?'1':'0');の部分がよく理解できません。
例えば５５という数字はどのように動かされて
2進数に変換されるのが教えてください

int count_bits(unsigned x)
{
  int count=0;
  while(x){
    if(x&1U)count++;
    x>>=1;
  }
  return (count);
}

int int_bits(void)
{
  return(count_bits(~0U));
}

void print_bits(unsigned x)
{
  int i;
  for(i=int_bits()-1;i>=0;i--)
      putchar(((x>>i)&1U)?'1':'0');
}

int main(void){

  unsigned nx;
  printf("type non negative");
  scanf("%u",&nx);

  print_bits(nx);
  putchar('\n');

  return 0;
}

コード

Answer 1

【普通の解説】
※ 宗教的な理由で、unsignedは全てunsigned intと記述しています。
まず、int_bits()がunsigned intにおけるbitsの数になることは理解できているでしょうか？もし、unsigned intが32bitsならint_bits()は32を返します(ぶっちゃけ、sizeof(unsigned int) * CHAR_BITでもいい気がするのですが)。次に、for(i=int_bits()-1;i>=0;i--)の部分ですが、iについて、31(-1しているので32ではありません)から0までforループで回すという意味です。あとはforループの中身を見ればわかるはずです。

forループの中身ですが、x>>iが何をしているかというと、xをi分だけシフトするという意味です。たとえば、xが55という数字の場合、2進数では下記になります。

x: 0000 0000 0000 0000 0000 0000 0011 0111
※ わかりやすいように、4bits毎にスペースで区切っています。

そして、iは31から始まりますので、まずは31個分左にシフトし、下記になります。

x >> 31: 0000 0000 0000 0000 0000 0000 0000 0000

全て0になりました。iが31から6までは同じようにすべて0になります。ビットが一切立ってないので、ここまでは0ということです。そして、0は偽なので三項演算子の部分は'0'が返り、0が表示されます。ではiが5の場合はどうなるかというと、

x >> 5: 0000 0000 0000 0000 0000 0000 0000 0001

と、最後に一つだけ残ります。次に1Uはなにかというと下記のようになっています。

1U: 0000 0000 0000 0000 0000 0000 0000 0001

この二つを&で演算すれば、

(x >> 5)&1U: 0000 0000 0000 0000 0000 0000 0000 0001

となり、つまり、左から6番目(5番目ではありません。判断するのはi+1番目です)のビットが立っているかがわかると言うことです。そして、1は真なので三項演算子の部分は'1'が返り、1が表示されます。同じようにiが4の場合は、

x >> 4: 0000 0000 0000 0000 0000 0000 0000 0011
1U: 0000 0000 0000 0000 0000 0000 0000 0001
(x >> 4)&1U: 0000 0000 0000 0000 0000 0000 0000 0001

となり、5番目のビットが立っていると判断できます。では3の場合はどうでしょうか？

x >> 3: 0000 0000 0000 0000 0000 0000 0000 0110
1U: 0000 0000 0000 0000 0000 0000 0000 0001
(x >> 3)&1U: 0000 0000 0000 0000 0000 0000 0000 0000

おお、0になりますね。つまり4番目のビットは立っていない、なので0なのです。あとは同じように、0までするだけです。

x >> 2: 0000 0000 0000 0000 0000 0000 0000 1101
1U: 0000 0000 0000 0000 0000 0000 0000 0001
(x >> 2)&1U: 0000 0000 0000 0000 0000 0000 0000 0001 # 3番目はビットが立ている

x >> 1: 0000 0000 0000 0000 0000 0000 0001 1011
1U: 0000 0000 0000 0000 0000 0000 0000 0001
(x >> 1)&1U: 0000 0000 0000 0000 0000 0000 0000 0001 # 2番目はビットが立ている

x >> 0: 0000 0000 0000 0000 0000 0000 0011 0111
1U: 0000 0000 0000 0000 0000 0000 0000 0001
(x >> 0)&1U: 0000 0000 0000 0000 0000 0000 0000 0001 # 1番目はビットが立ている

結果、00000000000000000000000000110111が表示されることがわかると思います。

---

【おまけ】
汎用性を持たせてみました。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>

#define UINTMAX_BITS_SIZE (sizeof(uintmax_t) * CHAR_BIT)
#define print_bits(x) print_bits_n((x), sizeof(x) * CHAR_BIT)

int count_bits(uintmax_t bits);
void print_bits_n(uintmax_t bits, int width);

int main(void)
{
        unsigned int nx;
        printf("type positive number (%u..%u): ", 0, UINT_MAX);
        if (scanf("%u",&nx) != 1) {
                printf("not number");
                exit(1);
        }

        print_bits(nx);
        putchar('\n');
        printf("%d\n", count_bits(nx));

        return 0;
}

int count_bits(uintmax_t bits)
{
        for (int i = 1; i < UINTMAX_BITS_SIZE; i <<= 1) {
                uintmax_t mask = (UINTMAX_C(1) << i) - 1;
                for (int j = (i << 1); j < UINTMAX_BITS_SIZE; j <<= 1) {
                        mask += mask << j;
                }
                bits = (bits & mask) + (bits >> i & mask);
        }
        return (int)bits;
}

void print_bits_n(uintmax_t bits, int width)
{
        for (int i = width - 1; i >= 0; i--) {
                putchar(bits & (UINTMAX_C(1) << i) ? '1' : '0');
        }
}

特徴は下記の通りです。

1. 参考サイトのバージョン5を汎用化。いくらでも大きく、かつ、unsignedで処理が可能に。(ただ、高速を目指すなら、mask値はテーブル化やメモ化すべきだろうが、面倒だったのでそこまではしてない)
2. unsigned intの大きさが16bitsでも、32bitsでも、64bitsでも、128bitsでも、256bitsでもいくらでも大きくてもたぶん大丈夫。
3. 表示は普通に上からビット演算することで、単純化。ただし、速くなるかどうかはわからない。 (あらかじめテーブル作ったら速くなりそう)
4. 符号有り整数で負の値を渡すと、カウントはうまくいかないので、unsignedでキャストしてから、渡してね。unsignedなら正しく暗黙的キャストするので何でもOK。
5. C99にちゃんと対応していないコンパイラでは通らない。(GCCとClangで確認済み、Visual Studioは未確認)

＞ katoyさん
参考サイトのバージョン4をunsignedにしたり、汎用化するのは私には無理でした。ごめんなさい。代わりにバージョン5で対応したので、許してください。

Comments

[reotantan]

ありがとうございました、とても助かります

Answer 2

#include  <stdio.h>

// https://msdn.microsoft.com/ja-jp/library/s3f49ktz.aspx
//   unsigned __int32  0 ～ 4,294,967,295

#define MSB (~( -1U >> 1 ))

// See http://www.nminoru.jp/~nminoru/programming/bitcount.html
//  ビットを数える・探すアルゴリズム
int count_bits(unsigned bits) {
  int num  = 0;

  for ( ; bits != 0 ; bits &= bits - 1 ) {
    num++;
  }

  return num;
}

int count_bitsx(int bits) {
  int num;

  num = (bits >> 1) & 03333333333;
  num = bits - num - ((num >> 1) & 03333333333);
  num = ((num + (num >> 3)) & 0707070707) % 077;

  return num;
}

void print_bits(unsigned val) {
  for (unsigned mask = MSB; mask; mask >>= 1) {
    if (val & mask) {
      putchar('1');
    } else {
      putchar('0');
    }
  }
}

int main(void) {
  unsigned nx;

  printf("type non negative (0..4294967295) ");
  scanf("%u",&nx);

  print_bits(nx);
  putchar('\n');
  printf("0x%x\n", nx);
  printf("count bit: %d\n", count_bits(nx));
  printf("count bit: %d\n", count_bitsx(nx));

  return 0;
}

実行例

$ gcc bit.c 
$ ./a.out
type non negative (0..4294967295) 7
00000000000000000000000000000111
0x7
count bit: 3
count bit: 3

$ ./a.out
type non negative (0..4294967295) 4294967295
11111111111111111111111111111111
0xffffffff
count bit: 32
count bit: 30

参考サイト http://www.nminoru.jp/~nminoru/programming/bitcount.html にあった count_bitsx() は int では動作しますが、unsinged では動作しません。
4294967295 のビット数が 30 となってしまいました。
32 が返ってｋるように修正する方法がわかる方は投稿をしていただれば幸いです。

Comments

[reotantan]

ありがとうございます、とても参考になりました！

[退会済みユーザー]

どうもcount_bitsx関数の計算方法だと、最上位２ビットを処理できないようですね。
似たような計算式に MIT HACKMEM というものがあるようですよ。

int bitcount (unsigned long long n)
{
unsigned long long tmp;

tmp = n
- ((n >> 1) & 0333333333333333333333ull)
- ((n >> 2) & 0111111111111111111111ull);

tmp += tmp >> 3;
return (tmp & 0707070707070707070700ull) % 63
+ (tmp & 7);
}

Answer 3

#include <stdio.h>

#define MSB ~( -1U >> 1 )

int main(void)
{
unsigned int bit;
unsigned int value;

printf("unsigned int = ");
scanf("%u",&value);
printf("Binary notation = ");

for ( bit=MSB; bit != 0; bit >>= 1 ) {
	if ( value & bit ) {
		putchar('1');
	} else{
		putchar('0');
	}
}
putchar('\n');

return 0;

}

処理説明
１．標準入出力ライブラリをインクルード
２．unsigned intの最上位ビットを定義
３．メイン関数定義
４．変数を定義
５．「unsigned int = 」を表示
６．unsigned int型で入力
７．「Binary notation = 」を表示
８．for文でMSBをbitに入れ、右シフトし、0になるまで以下の2つの処理を繰り返す。
8.1.該当ビットがONだったら、1を出力
8.2.該当ビットがOFFだったら、0を出力
９．改行を出力
１０．終了
※ なるべく、コードを省略しない方が読みやすくなります。
※ ビットカウントのアルゴリズムは、下記も参考にして下さい。追記：2015.08.29 20:54
bits = bits - ((bits >> 1) & 033333333333) - ((bits >> 2) & 011111111111);
bits = ((bits + (bits >> 3)) & 030707070707) % 077;

Comments

[reotantan]

丁寧な説明ありがとうございます。

Answer 4

こういうことでしょうか。
上手い指摘を思いつかなくて、実装をそのまま書いてます…ごめんなさい。

#define MSB_ON ~( -1U >> 1 )
void print_bits(unsigned x)
{
    int i;
    for(i=int_bits()-1;i>=0;i--){
        putchar((x&MSB_ON)?'1':'0');
        x<<=1;
    }
}

元の処理だと、以下の問題があります。
・xの内容が更新されない
・１ビットシフト後に最下位ビットの評価を行うので入力値の最下位ビットが評価前に捨てられる

また最後に表示するビットの並びが逆転しているので、上記のコードは最上位ビットを評価するようにしています。

Comments

[退会済みユーザー]

動作の流れを追いたいという話でしたら、むしろデバッガの使い方を覚えて、ステップ実行してみることをお勧めします。
たぶん人に聞くよりもその方が具体的に分かる事も多いと思います。

Windowsの場合はVisualStudio、Macの場合はXCodeを用いればデバッグは非常に楽にできるので、デバッガの使い方を調べてみてはどうでしょう。

＞VisualStudioでの例
http://visualstudiostudy.blog.fc2.com/blog-entry-8.html

ちなみに、1 -> i に更新されたprint_bits関数のfor文は（最上位ビットから順に）最下位ビットに評価したいビットの値をシフトしています。
32bit幅だったら、x>>31, x>>30, x>>29 ... x>>2, x>>1, x>>0というように１ビットずつ。合計３２回ビットの評価をしています。

[reotantan]

なるほど、理解が進みました。
ありがとうございます