ハッカーのたのしみ -本物のプログラマはいかにして問題を解くか-

大昔に買ったままちゃんと読んでなかったんだけど久しぶりに読んでみたら昔よりよく理解できました。これをすらすら理解できるようになるとハッカーに一歩近づけるのだろうか(笑)

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

ビットのカウント

実はライフゲームで以前この本で学んでとても気に入っているテクニックを使っています。→ソース

int count_bit(unsigned int x)
{
  int n = 0;
  while(x != 0){
    ++n;
    x &= x-1;
  }
  return n;
}

これは1のビットの立っている個数をカウントする関数で、ライフゲームではセルの近傍の生きているセルを数える為に使っています。
ポイントは

x &= x-1;

の部分でこれはxのうち一番右のビットをオフにするという操作をしています。1を引いたときの繰り下がりを使ってうまくマスクを作っているんですね〜。
for文より簡単にかけるので私は好きな書き方です。速度はfor文を使った場合の約2倍でした。*1

上と同じ関数は

int count_bit(unsigned x)
{
  x -= ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x += (x >> 8);
  x += (x >> 16);
  return x & 0x0000003F;
}

と書けます。これは分割統治による数え方でこれを使うと上の方法より４倍以上!速くなります。
1行めはxを２ビットずつ区切って個数をカウント、2行めは4ビットずつ3行めは8ビットずつ…という要領です。最初にこの計算を見たときはびっくりしたんですが、じっくりビット列の変化を見てみるとそれぞれがどういう事をしているのかが分かって非常に勉強になりました。
さすがにこれは自分でも読みにくいのであまり使いませんが…。

こういうビット演算のテクニックを勉強すると純粋に面白く、シミュレーションなど速度が重視されるプログラミングでは意外と実用的だったりします。

ビットの入れ換え

次の計算は私が作ってみたものですが、32ビットマシンでxが8ビット整数の場合に下位から偶数番目のビットのみ取り出してさらにそれを逆順にするという操作をしています。

((x * 0x04004004) & 0x20080208) % 511

ex.)
x = 10011010 ならば上式の値は 1101 となる

ここで使ってるテクニックを覚えた時には感動しました。乗算と剰余算のこのテクニックで自由自在にビットを操れるようになります。*2
長くなってしまったので詳しくはまた今度書いてみます。

*1:可読性は低下するので、趣味でのコーディングにとどめるべきですが…

*2:これは割り算があるのでテーブル検索した方が高速です。