【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※返信付き投稿の削除は禁止!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら


本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.22269

はじめまして
投稿者---ごろう(2005/07/29 01:38:02)


こんばんわ^^最近C言語の勉強を始めました。ごろうです。よろしくお願いします。さっそくなんですが
#include <stdio.h>
int num(int);
int main(void){
int x;
printf("input x:");
scanf("%d",&x);
printf("n = %d\n",num(x));
return 0;
}
int num(int bits){
bits = (bits & 0x55555555) + (bits >> 1 &0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 &0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 &0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 &0x00ff00ff);
return (bits & 0x0000ffff) + (bits >>16 &0x0000ffff);
}
というプログラムがどういう動作をしているのかがイマイチわかりません。誰か教えていただけませんか?



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:はじめまして 22275 Blue 2005/07/29 08:39:08
<子記事> Re:はじめまして 22276 tetrapod 2005/07/29 09:12:31


No.22275

Re:はじめまして
投稿者---Blue(2005/07/29 08:39:08)


> イマイチわかりません。
どこがイマイチわからないのか全然わかりません。

> bits & 0x55555555
ですか?

> bits >> 1 &0x55555555
ですか?

もう少し具体的に書いたほうがよいでしょう。

それと
>> ※題名は具体的に!
>> ※ソースの添付は「HTML変換ツール」で字下げ!
>> by 掲示板ご利用上の注意
です。

次回の投稿から気をつけてください。



この投稿にコメントする

削除パスワード

No.22284

Re:はじめまして
投稿者---ごろう(2005/07/29 11:28:12)


><pre>> イマイチわかりません。
どこがイマイチわからないのか<b>全然</b>わかりません。

> bits & 0x55555555
ですか?

> bits >> 1 &0x55555555
ですか?


もう少し<big><b><font color="red">具体的</font></b></big>に書いたほうがよいでしょう。

それと
>> ※題名は具体的に!
>> ※ソースの添付は「HTML変換ツール」で字下げ!
>> by <a href="http://www9.plala.or.jp/sgwr-t/c_sub/bbs.html" target="_balnk" title="掲示板ご利用上の注意">掲示板ご利用上の注意</a>
です。

次回の投稿から気をつけてください。</pre>

すみません。次回から気をつけます。そうです、関数numの中身がどういう動作がおこなっているかがわかりません…


この投稿にコメントする

削除パスワード

No.22384

Re:はじめまして
投稿者---かずま(2005/08/03 03:08:58)


> すみません。次回から気をつけます。そうです、関数numの中身がどういう
> 動作がおこなっているかがわかりません…

気を付けますといっておきながら、全然気をつけていないじゃないですか。

【掲示板ご利用上の注意】を全く無視し、全文引用を行い、自分の書いたもの
と人の書いたものの区別がつかない書き方をしていることに気づきませんか?

関数 num の説明はしません。説明のほうは ここでも見てもらうことにして、
私は全く異なる方法を示します。悩んでください。
#include <stdio.h>

int num(unsigned long b)
{
    #define T0(x) x,x+1
    #define T1(x) T0(x),T0(x+1)
    #define T2(x) T1(x),T1(x+1)
    #define T3(x) T2(x),T2(x+1)
    #define T4(x) T3(x),T3(x+1)
    #define T5(x) T4(x),T4(x+1)
    #define T6(x) T5(x),T5(x+1)
    #define T7(x) T6(x),T6(x+1)
    static char t[] = { T7(0) };
    return t[b>>24] + t[b>>16 & 255] + t[b>>8 & 255] + t[b & 255];
}

int main(void)
{
    unsigned long x;

    while (printf("> "), scanf("%lx", &x) == 1)
        printf(" %d\n", num(x));
    return 0;
}



この投稿にコメントする

削除パスワード

No.22276

Re:はじめまして
投稿者---tetrapod(2005/07/29 09:12:31)


http://www.nminoru.jp/%7Enminoru/diary/2003/09.html#2003-09-11
を見た後で解説をよみませう。
http://macinbasic.info/modules.php?name=News&file=article&sid=479

元発言のプログラムは unsigned int でないので、その意味で間違いあり。



この投稿にコメントする

削除パスワード

No.22278

Re:はじめまして
投稿者---かずま(2005/07/29 09:55:15)


> 元発言のプログラムは unsigned int でないので、その意味で間違いあり。

どこが間違いかをもっと詳しく説明していただけませんか?

int の場合、右シフトで符号ビットが保存され、上位のビットに拡張されますが、
それは &演算ですべて 0 になりますので、bits の型は int でも何の問題も
ないはずです。


この投稿にコメントする

削除パスワード

No.22287

Re:はじめまして
投稿者---tetrapod(2005/07/29 12:18:02)


2の補数系でないマシンでも大丈夫でしょうか?
符号ビット+絶対値の処理系で -1 >> 1 は 0 になる可能性があります。
(負数のシフト結果は処理系定義)
0x80000001 >> 1 は 符号ビットを残して 0x80000000 になればいいけど、
負の0に対して正規化が行われると 0x00000000 になります。
すると最終結果は1になりそうですけど。



この投稿にコメントする

削除パスワード

No.22288

Re:はじめまして
投稿者---ごろう(2005/07/29 12:23:59)


>2の補数系でないマシンでも大丈夫でしょうか?
>符号ビット+絶対値の処理系で -1 >> 1 は 0 になる可能性があります。
>(負数のシフト結果は処理系定義)
>0x80000001 >> 1 は 符号ビットを残して 0x80000000 になればいいけど、
>負の0に対して正規化が行われると 0x00000000 になります。
>すると最終結果は1になりそうですけど。

どうも、おぎやはぎですw
もう少し簡単に説明してもらえないでしょうか?


この投稿にコメントする

削除パスワード

No.22308

Re:はじめまして
投稿者---かずま(2005/07/30 02:18:59)


> 2の補数系でないマシンでも大丈夫でしょうか?

負数の右シフトが処理系定義なので、確かに「符号+絶対値」や「1の補数」表
現のマシンでは結果が予想できませんね。もっとも計算機の黎明期ならいざし
らず、「2の補数」表現以外のマシンが存在し、そこで C が動いているとは
思えませんが、....。

規格上は、unsigned にしたほうが確実な結果が得られるということですね。
ありがとうございました。


この投稿にコメントする

削除パスワード

No.22286

Re:はじめまして
投稿者---ごろう(2005/07/29 12:00:12)


>http://www.nminoru.jp/%7Enminoru/diary/2003/09.html#2003-09-11
>を見た後で解説をよみませう。
>http://macinbasic.info/modules.php?name=News&file=article&sid=479
>
>元発言のプログラムは unsigned int でないので、その意味で間違いあり。

↑のページ読んでみたのですがビットの概念がよくわからないもので、頭混乱して終りました(泣)


この投稿にコメントする

削除パスワード

No.22316

Re:はじめまして
投稿者---si(2005/07/31 03:02:03)


>>http://www.nminoru.jp/%7Enminoru/diary/2003/09.html#2003-09-11
>>を見た後で解説をよみませう。
>>http://macinbasic.info/modules.php?name=News&file=article&sid=479
>>
>>元発言のプログラムは unsigned int でないので、その意味で間違いあり。
>
>↑のページ読んでみたのですがビットの概念がよくわからないもので、頭混乱して終りました(泣)

課題のルーチンの解説(間違っていれば訂正、お願いします)
(ルーチンA)
int bit_cnt(int bits){
    bits = (bits & 0x55555555) + (bits >> 1 &0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 &0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 &0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 &0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 &0x0000ffff);
}

まず、&(and)演算する定数値の2進数表現
(これが分かったら、80%は理解したと同じ)
0x55555555 = 0b010101...
0x33333333 = 0b00110011...
0x0f0f0f0f = 0b0000111100001111...
0x00ff00ff = 0b0000000011111111...
0x0000ffff = 0b00000000000000001111111111111111

bit演算部
bits & 0x55555555 -> 奇数bitの保存
bits >> 1 & 0x55555555 偶数bitの保存

bits = (bits & 0x55555555) + (bits >> 1 &0x55555555);
保存した、奇数、偶数bitを足すことで、
奇数偶数bitペアの立っているビット数を保存
これを倍数単位(32ビット整数値の場合 1、2、4、8、16)で繰り返えし
立っているbitをカウントする。
右シフト命令は、sar(shift arithmetic right)なので、
MSD(最上位桁most significant digit)は、そのまま拡張されるが、
(LSD least significant digit 最下位桁)
&演算時に捨てられるので、負数の考慮は不要



この投稿にコメントする

削除パスワード

No.22348

Re:はじめまして
投稿者---tetrapod(2005/08/01 10:34:31)


正しい解説だと思いますが、ある程度わかっている人向けなように思えます。
元発言者様は「ビット」が何かわかっていないようなので、
その説明だけで納得できるかどうかはまた別でしょう。

ビット=2進数の1桁のこと、つまり0か1か。
32bit というのは2進数で32桁のことです。
数値 100d は、2進数で 1100100b ですが、例題はこの1の数を数える、
つまり 100d に対しては 3d を返す、というものです。
数値 125d なら 1111101b なので 6d を得ます。
(xxxd とは10進数を yyyb とは2進数を表記するつもり)

んでここまでわかっていれば別解説とか
http://www.st.rim.or.jp/~phinloda/cqa/cqa15.html

2ビット数の中の1の数を数えるのに必要な処理が
「隣り合う奇偶ビットを桁そろえして加える」だけでいい
のがわかればまさに80%理解したも同然ですね。



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧