ビットデータのチェック方法

C言語でのビットデータのチェック方法についての質問です。

例として、以下のようなのビット（0～31）を用意して
unsigned int bit;
bit = 010100…00101
という風にデータを与えているとします。

このとき、ビットに1を持つ桁の個数を数えて
010000→1個　、001001 →1個以上
という風に1個しかないか、それ以上あるかを高速で判定したいのですが、どのような方法が考えられるでしょうか。

私が考えた方法としては
count = 0;
for (i=0 ; i < 32 ; i++){
if ((bit >> i)%2 == 1) count++;
if (count > 1) break;
}
//countが1なら個数は1個、countが0か1以上なら1個でない。

という方法も行いましたが、処理が遅くなってしまいます。
各桁が1の場合(00…010等)のデータを用意しておき、ビットの値を連想配列へ入れて判別するという方法も考えましたがC言語では無理なようです。

可読性や汎用性は問わないものとして、何か良い方法は無いでしょうか？
ご存知の方いらっしゃいましたらよろしくお願いします。

No.5 ベストアンサー 回答者： Oh-Orange 回答日時： 2007/12/28 17:41

★アドバイス

・次のリンクを参考にして下さい。
　http://www.nminoru.jp/~nminoru/programming/bitco …→『ビットを数える・探すアルゴリズム』
　このリンクのバージョン5を使って立っているビットの数が 1 か、それ以外で判定します。
　なお、考え方は回答者No.1さんで紹介されているリンクと同じです。
・回答者No.2さんの方法では double 型を使う関数を利用しています。
＞対数を取得し、整数値のみであれば、ビットが一つと考えればよいと思います
　↑
　log、fmod関数を使うよりも単純にビットをシフトしてカウントした方が高速な気がします。
　その他『ビット カウント』キーワードで検索すると多数情報がでます。
　以上。

参考URL：http://www.nminoru.jp/~nminoru/programming/bitco …

この回答へのお礼

いろいろな方法があり、大変勉強になりました。
回答者No.1さんに紹介していただいた「ハッカーのたのしみ」は以前から興味があった本なので今度読んでみたいと思います。

みなさんありがとうございました。

お礼日時：2007/12/28 23:20

No.4 回答者： zwi 回答日時： 2007/12/28 17:28

インラインアセンブラで書けば、ローテイトと加算をループするだけなので高速に処理できそうですが、Ｃ言語だけとなると#3のtatsu99さんの回答が最適解かもしれません。

こういうコードを高速化する場合は、アセンブルコードを見ながらやらないと良いコードが確認できませんので注意してください。もちろん、リリースビルド(最適化)して実行することも必要です。

No.3 回答者： tatsu99 回答日時： 2007/12/28 16:17

理想的には

char data[4294967296];として、
その添え字が、unsigned int 0～4294967295をとるようにします。
ここで、１ビットであるのは、1,2,4,8,16,....,2147483648ですので、
その添え字に該当するところに、1を設定し、以外は,0を設定しておきます。
そうすると、if (data[x] == 1)が成立した場合のみ、xは１ビットであると、判断できます。
この方法の欠点は、非常に大きなサイズ（４Ｇ）のメモリを浪費するところにあります。
その為、考え方は同じですが、メモリを消費しない別案が、以下の方法です。
char data[65536];の領域をとります。
この添え字が、1,2,4,8,16,...,32768のところのdataを１、以外を０にします。
xの上位１６ビットと下位１６をそれぞれ取り出します。(x1,x2とします）
data[x1] == 1 && data[x2]==0 が成立するか
data[x1] == 0 && data[x2]==1 が成立すれば、xは１ビットで構成されていることになります。
又は、(data[x1]+data[x2]==1)が成立するかの判定でもかまいません。
上記の方法は、実測してませんので、効果がなかったら、ごめんなさい。

No.2 回答者： Schwarz20 回答日時： 2007/12/28 15:13

ビットが一つのみ「１」となっているときは、２のｎ乗の値となので

対数を取得し、整数値のみであれば、ビットが一つと考えればよいと思います

if (! bit)
　　// ビットが０個のときの処理
else if (fmod(log(bit) / log(2.0), 1.0) > 0.0)
　　// ビットが一つ以上の処理
else
　　// ビットが一つのときの処理

No.1 回答者： sakusaker7 回答日時： 2007/12/28 15:07

ほい。

count of bits in a long - comp.lang.c | Google Groups
http://groups.google.com/group/comp.lang.c/msg/b …

こういった話題は
Amazon.co.jp： ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか: 本: ジュニア,ヘンリー・S. ウォーレン,Jr.,Henry S. Warren,滝沢 徹,赤池 英夫,藤波 順久,鈴木 貢,葛 毅,玉井 浩
http://www.amazon.co.jp/dp/4434046683

に満載されています :)