質問: 1バイトの文字中に立っているビットの数をスマートに数える方法を ご存じの方、ご教示いただけませんでしょうか。 ライフゲームを作成しようと構想した際に、周りのセルの状態をビットで表現すれば 次世代の行動(繁殖、維持、死滅)が判断できると思った事からこう考えるに至りました。 ビットを立てる立てないの準備段階でカウントすればいいじゃないかと、まったくの無駄手間だと 思いこの方式は使わない事にしましたが、今はこっちの方をパズル感覚で思案中です。 ・ビットマスクして各ビットのオン/オフを数える方法 ・シフトしてキャリーを調べる方法 の2点が思いついたのですが、どちらにしろループが必須で今一つ、スマートさに 欠ける気がしまして、諸兄のお力を拝借したく存じます。 妙案をお持ちの方、どうぞよろしくお願いします。
回答: 1バイト(8ビット)で立っているビット数を数えるぐらいなら、値と立っているビット数のテーブルを用意しておいて、それを参照するのが早いです。 ``` // 0x00~0xffの立っているビット数のテーブルを用意する int raisedBits[256] = {0,1,1,2,1, ... ,7,8}; ``` というようにテーブル(数表)を用意しておけば、 ``` // 1バイトの変数 n に立っているビット数が、配列の参照1回で判る bits = raisedBits[n]; ``` のように配列から要素を取り出すだけで、ループを使わずにビット数が判りますし、処理速度も速いです。(数表は最初に作って、それを何度も利用する事。毎回数表を作っていては、処理が遅くなります) トリッキーですが、案外役に立つテクニックです。