今日はコードを2つ紹介(出典: ハッカーのたのしみ, Henry S. Warren, Jr., 滝沢ら訳)しますがどれもメチャクチャわかりづらいです。どちらも可読性なんかかなぐり捨ててとにかく効率を追った、ある意味潔いコードです。GNU netcatも中途半端に読みづらい変なコードを書くくらいなら、このくらいやって欲しかったなあ。
本についてですけど、前半はまだわかる気がしますが、後半はあまりにも頑張りすぎていて全然わからんです…。こういうコードを読んでいると、根性っていうか、ハッカー達の職人魂みたいなものを感じますよ。
さて1になっているビットを数える処理ですが、比較的わかりやすいコードを一つ例にとってみようと思います。
unsigned int x;
int count;
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
count = x;
以上は32ビット用のコードです。ぱっと見だと、なんじゃこりゃ?って感じですね。このコードでは隣り合う桁を足していきます。最初は隣の1桁、次は2桁、次は4桁という風に倍々ゲームにしていきます。
では8ビットで検証してみます。
x = [ 1][ 0][ 1][ 1][ 0][ 1][ 0][ 0] 1ビット毎の : 1, 0, 1, 1, 0, 1, 0, 0 1の個数 : x = [ 1][ 0][ 1][ 1][ 0][ 1][ 0][ 0] x>>1 = [ 1][ 0][ 1][ 1][ 0][ 1][ 0][ 0] 0x55 = [ 0][ 1][ 0][ 1][ 0][ 1][ 0][ 1] x&0x55 = [ 0][ 0][ 0][ 1][ 0][ 1][ 0][ 0] (x>>1)&0x55 = [ 1][ 0][ 1][ 0][ 0][ 0][ 0][ 0] x = [ 0 1][ 1 0][ 0 1][ 0 0] 2ビット毎の : 1 + 0 = 1, 1 + 1 = 2, 0 + 1 = 1, 0 + 0 = 0 1の個数 : x = [ 0 1][ 1 0][ 0 1][ 0 0] x>>2 = [ 0 1][ 1 0][ 0 1][ 0 0] 0x33 = [ 0][ 0][ 1][ 1][ 0][ 0][ 1][ 1] x&0x33 = [ 0 0][ 1 0][ 0 0][ 0 0] (x>>2)&0x33 = [ 0 1][ 0 0][ 0 1][ 0 0] x = [ 0 0 1 1][ 0 0 0 1] 4ビット毎の : 1 + 2 = 3, 1 + 0 = 1 1の個数 : x = [ 0 0 1 1][ 0 0 0 1] x>>4 = [ 0 0 1 1][ 0 0 0 1] 0x0f = [ 0][ 0][ 0][ 0][ 1][ 1][ 1][ 1] x&0x0f = [ 0 0 0 0][ 0 0 0 1] (x>>4)&0x0f = [ 0 0 1 1][ 0 0 0 1] x = [ 0 0 0 0 0 1 0 0] 8ビット毎の : 3 + 1 = 4 1の個数 : よってxには1が4つ含まれていた。
このように検証してみますと、1の数を倍々でまとめていって最後にはxの右端にビットの個数が集約されて計算されることが分かります。凄いんですけど、なんともトリッキーですねえ。
もう一つ似たようなコードで、パリティを求める処理が書けます。単純にパリティを求めるならば、全てのビットのxorを取れば良いのですが、この本では以下のように書きます。
unsigned int x, y;
int parity;
y = x ^ (x >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >> 16);
parity = y & 1;
以上は32ビット用のコードです。やはりこれもぱっと見では、なんじゃこりゃ?って感じです。これも2進数の1桁分, 2桁分, 4桁分…とxorを取っていって最後に32桁分のxorがyの右端に来るという仕掛けです。
では8ビットでの計算の結果をご覧下さい。
x = [ 7][ 6][ 5][ 4][ 3][ 2]( 1)( 0) `-----| xor x>>1 = [ 7][ 6][ 5][ 4][ 3][ 2]( 1)[ 0] y = [ 7][ 7,6][ 6,5][ 5,4][ 4,3]( 3,2)[ 2,1]( 1,0) `-----------| xor y>>2 = [ 7][ 7,6][ 6,5][ 5,4][ 4,3]( 3,2)[ 2,1][ 1,0] y = [ 7][ 7,6][ 7-5]( 7-4)[ 6-3][ 5-2][ 4-1]( 3-0) `-----------------------| xor y>>4 = [ 7][ 7,6][ 7-5]( 7-4)[ 6-3][ 5-2][ 4-1][ 3-0] y = [ 7][ 7,6][ 7-5][ 7-4][ 7-3][ 7-2][ 7-1]( 7-0) ~~~~~~
このように検証してみますと、うまく各桁が一回ずつxorされるようにずらしながら計算していることがわかります。最後に yの右端に全てのビットのxorが計算されているのが見事ですね。
現在はコンピュータが十分高速化していて、ソフトウェアの規模も大きくなっているため、速度より保守性を重視します。要は遅くて良いから誰もが読める普通のコードが求められます。どんなに速くても誰も理解できないトリッキーなコードは歓迎されません。
ただしそれは商業サーバー用のプログラムとかPC用のプログラムでの話。もっと特殊な分野、例えば究極の速度を求める超高性能計算(計算用のライブラリとか)や、ハードがショボショボな組み込み機器などは、無駄に使えるCPUやメモリがありません。というわけで、まだまだトリッキーなコードも出番があるんじゃないかなあ?
< | 2007 | > | ||||
<< | < | 11 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
- | - | - | - | 1 | 2 | 3 |
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | - |
合計:
本日: