Fussy's Diary

先ほど「アルゴリズムのコーナー」を更新しました。

今回のお題は「適応型ハフマン符号化」です。サンプル・プログラムの作成に結構苦戦しました。ほぼ完成したと思っていた夕方頃にバグを見つけたときは、今日の更新は無理かなと思っていました。

今回見つけたバグは次のようなものです。

~0 << l

で、0 のビット反転結果を l だけ左シフトできます。左辺が 32 ビットなら l が 32 のときはゼロになってしまうはずですが、なぜかゼロにならず、ビットシフトが全くされなくなります。しかし、

~0 << 32

と書けばちゃんとゼロになります。型のサイズより大きくビットシフトしている場合、コンパイラが勝手に剰余を求めてくれるのか、それとも他に理由があるのか、そこまではわからなかったのですが、最終的には l の大きさを見て計算方法を切り替えるようにしました。少々気持ち悪い感じはしますけどね。