hm7:
my best friend
DS版のゴースト トリックは，筆者を含め，実際にプレイした人の多くが高く評価している作品だが，残念ながらセールス的には期待したところまで届かなかったというのも事実。ビジネス的に見れば，続編が作られないまま“終わってしまう”可能性もあるだろう。
“
| — | 4Gamer.net — DS版「ゴースト トリック」の開発スタッフが直接移植。発売後半年でiPhone/iPod touch版リリースに至った経緯を，プロデューサーの竹下博信氏に聞いてきた（ゴースト トリック） (via otsune) |
バージョン4
ここからが管理人がショックを受けたアルゴリズム。
バージョン 4 ではループを使用しないでも ビットカウント操作ができてしまっている。
int numofbits4(int bits) {
int num;
num = (bits >> 1) & 03333333333;
num = bits - num - ((num >> 1) & 03333333333);
num = ((num + (num >> 3)) & 0707070707) % 077;
return num;
}
バージョン5
ビットを数える最適化されたアルゴリズム。
このアルゴリズムではループ・条件分岐がないばかりか、 剰余命令まで消失している。 現在のスーパースカラープロセッサでは 演算を畳み込めるので、 CPU にビルトインしたビットカウント命令よりも このアルゴリズムを用いた方が 高速に処理ができると思われる。
int numofbits5(long bits) {
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}
上記のアルゴリズムは、バージョン4 が Knuth の本に、バージョン5 が 参考文献 にあげた Hacker’s Delight に載っている。
“
| — | ビットを数える・探すアルゴリズム (via otsune) |
