11

ハミングウェイトに関するウィキペディアの記事を読んで、興味深いことに気づきました。

したがって、同じ長さのすべてゼロの文字列の from と同等Hamming distanceです。最も典型的なケースであるビットのストリングの場合、これはストリング内の 1 の数です。この2 進数の場合は、人口数、popcountまたは横方向の合計とも呼ばれます。

[鉱山を強調]

それで、何かが私に起こりました。XOR2 つの文字列をingし、結果の文字列のハミング ウェイト (POPCOUNT) を取得して、2 つの文字列間のハミング距離を計算できますか?

これに沿ったもの（gcc組み込み関数を使用）：

#include <stdint.h>

int hammingDistance (uint64_t x, uint64_t y) {
        uint64_t res = x ^ y;
        return __builtin_popcountll (res);
}

さて、なぜこれをしたいのかというと、一部のプラットフォームでは、そうです、これは単にgccを計算する関数への呼び出しを発行することに変換されますpopcount。たとえば、なしの x64popcntでは、gcc吐き出します ( Godbolt の GCC Online ):

hammingDistance:
    sub rsp, 8
    xor rdi, rsi
    call    __popcountdi2
    add rsp, 8
    ret

OTOH、POPCOUNT をサポートするプラットフォームを使用している場合、x64 モデルnehalem以降 (を含むPOPCNT) のように、( Godbolt の GCC Online )が得られます。

hammingDistance:
    xor rdi, rsi
    popcnt  rax, rdi
    ret

特にインライン化すると、これは非常に高速になるはずです。

しかし、元の質問に戻ります。2 つの文字列の XOR のハミング重みをとって、それらのハミング距離を見つけることができますか? すなわち:

HD = HW (x xor y)
4

2 に答える 2

6

2 つの等しい長さの文字列間のハミング距離xとyは、それらが異なる位置の数として定義されます。xとyがビットx^y文字列の場合、 は1s が異なる位置に正確にある文字列です。したがって、HammingDistance(x,y) = Number of 1s in x^yビット文字列の場合。また、HammingWeight(x) = number of 1s in xbitstring の場合x。したがって、最初の主張HammingDistance(x,y) = HammingWeight(x^y)はビット文字列に当てはまります。それを確立したので、実装が正しいことは明らかです。

于 2014-08-02T20:23:31.790 に答える
3

はい、うまくいきます。各ビットについて、入力ビットが異なる場合にのみビットが 1 になります。したがって、ビット ベクトル全体に適用すると、結果には、入力の異なるビット (HD) と同じ数の 1 ビット (HW) が含まれます。そして、あなたのコードはその関係を完全にうまく利用しているようです。実際、このショートカットは、リンク先のハミングの重みの記事 (効率的な実装)でさらに言及されています。

2 つの単語 A と B のハミング距離は、A xor B のハミング重みとして計算できます。

于 2014-08-02T20:21:34.283 に答える