22457


１バイトの文字中に立っているビットの数をスマートに数える方法を  
ご存じの方、ご教示いただけませんでしょうか。

ライフゲームを作成しようと構想した際に、周りのセルの状態をビットで表現すれば  
次世代の行動（繁殖、維持、死滅）が判断できると思った事からこう考えるに至りました。  
ビットを立てる立てないの準備段階でカウントすればいいじゃないかと、まったくの無駄手間だと  
思いこの方式は使わない事にしましたが、今はこっちの方をパズル感覚で思案中です。

・ビットマスクして各ビットのオン／オフを数える方法  
・シフトしてキャリーを調べる方法

の２点が思いついたのですが、どちらにしろループが必須で今一つ、スマートさに  
欠ける気がしまして、諸兄のお力を拝借したく存じます。

妙案をお持ちの方、どうぞよろしくお願いします。


CC BY-SA 3.0
2016-02-24T01:50:33.073
22456
2016-02-24T07:19:32.767
14459
question
アルゴリズム
立っているビットを数える方法


<http://graphics.stanford.edu/~seander/bithacks.html> の counting bitsets
が、求めている回答になるかと思います。


CC BY-SA 3.0
2016-02-24T01:57:58.643
22457
2016-02-24T01:57:58.643
754
22456
answer


１バイト（８ビット）で立っているビット数を数えるぐらいなら、値と立っているビット数のテーブルを用意しておいて、それを参照するのが早いです。

[code]

    // 0x00～0xffの立っているビット数のテーブルを用意する
    int raisedBits[256] = {0,1,1,2,1, ...  ,7,8}; 
    
[/code]

というようにテーブル(数表)を用意しておけば、

[code]

    // 1バイトの変数 n に立っているビット数が、配列の参照1回で判る
    bits = raisedBits[n];  
    
[/code]

のように配列から要素を取り出すだけで、ループを使わずにビット数が判りますし、処理速度も速いです。（数表は最初に作って、それを何度も利用する事。毎回数表を作っていては、処理が遅くなります）

トリッキーですが、案外役に立つテクニックです。


CC BY-SA 3.0
2016-02-24T07:19:32.767
22475
2016-02-24T07:19:32.767
217
22456
answer