昔、JavaのRandomクラスのnextInt(int)の実装を見たときの話だ。
ある数nが2のべき乗かどうかを判定するのにベーシックな素因数分解ではなく、2の補数の特性を活かして
if ((n & -n) == n) // i.e., n is a power of 2
と書かれていたのを見て、目から鱗が落ちるような感じになったのを覚えている。
本書ではこのようなbit演算に関するtopicを大量に纏めている。普段からこの本に書いてある内容のことをごりごり実装する人は多分いないだろうが、高速化に執念を燃やすコンパイラの世界や基幹ライブラリの中ではこのようなコードが蠢いているということが改めて意識できるかと思う。
本の雰囲気は大学の教科書に近い。というか、大学の教科書より難解だと思う。いくつかどうしても理解できないところがあった。訳本だからかな...。
難しいと感じたのは9,10章の除算関連。そらーunlovelyなワケですわ。
割り算をよりコストの少ない掛け算に変換するためのマジックナンバー抽出の話題が面白かった。(x / 3 が x * 0x55555556 に化けてしまうなんて...。)今、我々が計算機上で / 演算子を使って気軽に割り算できるのも先人の知恵と苦労の賜物なんだなぁとしみじみ感じたり。
特に面白く感じたのはp283の先頭桁の分布に関する話。
この世に溢れている数字を無作為に取ると、30%の確率でその数字は1で始まっているという話だ。数字は1から9まであるので(0始まりではない!)、ひどく直感に反する話だが数学的に証明されているのが面白い。
調べてみると、どうやらこの事象のことをベンフォードの法則というらしい。
読むのにえらい時間がかかったが、bit演算に関するtopic集だけに留まらない内容なので、数学等に興味あるプログラマー全てにオススメしたい。そんな一冊。
