すごくシンプルなハミング距離計算

Tweet

ハミング距離とはなんぞや……という話はWikipediaでも見ていだたくとして、要するに「ビット列を比較して値の異なる位置を数えたい」ということです。例えば01010011と01010111のハミング距離は1です。

異なるビット

二つのビット列のうち、ビットの異なる位置を抽出することは簡単です。基本です:

d = a ^ b;

ビットを数える

あとはここから立っているビットを数えるわけですが、普通に考えると

• ビット列の幅の分だけループさせる
• プロセッサのビットサーチ命令を使う

という方法を使うと思います。前者は当然遅いので嫌ですね。後者はインラインアセンブラを使ってプロセッサ依存にしないといけませんし、ビットマスクを作ってビットを消しながら数えなくてはならず、いかにも面倒です (←根拠もなくシフト命令は遅いと思っているヤツ)。

そこで私が使う方法は次のようなものです:

d &= d - 1; // 立っている最下位ビットを消す

全ビットが消えるまでループすればハミング距離が分かります:

d = a ^ b;
i = 0
while (d) {
  d &= d - 1;
  i++;
}

おしまい

このコードを何に使うのかというと、BCH(15,5)符号などをパターンマッチングで誤り訂正しようということだったりします。15ビットもあるのに内容は5ビット(32パターン)しかないので、ハミング距離が一番小さい符号語が訂正結果ということにした方が簡単なのではないかというわけです。別にガロア体がよく分からんとかそういう理由ではないんですよ。
Happy hacking!