デバッグ記録

先の実験（二月も終わりが見えてくる時期 - やた＠はてな日記）で新たにバグを発見したため，修正していました．

今回のバグは，大規模な LOUDS Trie と DFUDS Trie において，登録したキーを検索しても見つからないというものでした．キー数を 10 億件まで増やしても顕在化しなかったので，原因を見つけるまでに思いのほか時間がかかりました．

原因は以下のようなものでした．

z = (x >> ((y - 1) * 8)) & 0xFF;  // 修正前
z = ((x << 8) >> (y * 8)) & 0xFF;  // 修正後

危険なのは y が 0 のときなのですが，x の上位 8 ビットが 0 の状態では，演算結果 z が同じになります※．おかげで，ビット列の長さが 2^33 = 80 億ビット前後になるまで何の問題もなく動作するという厄介なことになっていました．

※ おそらく，右辺値が負数のとき，シフト演算の動作は未定義です．私の環境（64 ビット Ubuntu 9.04 + gcc 4.3.3）では，以下のような結果になっていました．予想の斜め上です．

for (int i = 1; i < 8; ++i)
  std::printf("~0U >> %d: %08X\n", -i, ~0U >> (-i));

// 出力
// ~0U >> -1: 00000001
// ~0U >> -2: 00000003
// ~0U >> -3: 00000007
// ~0U >> -4: 0000000F
// ~0U >> -5: 0000001F
// ~0U >> -6: 0000003F
// ~0U >> -7: 0000007F