4

面接の準備を始めたところ、次の問題に遭遇しました。

  • 整数の配列が与えられます
  • ここで、配列内の整数のすべてのペアのハミング距離の合計をバイナリ表現で計算します。

例：

given {1,2,3} or {001,010,011} (used 3 bits just to simplify)
result= HD(001,010)+HD(001,011)+HD(010,011)= 2+1+1=4;

純粋にブルート フォース ソリューションからの唯一の最適化は、ここで使用できることを知っていますが、ここに示すようにハミング距離の個々の計算にあります。

int hamming_distance(unsigned x, unsigned y)
{
    int       dist;
    unsigned  val;

    dist = 0;
    val = x ^ y;    // XOR

    // Count the number of bits set
    while (val != 0)
    {
        // A bit is set, so increment the count and clear the bit
        dist++;
        val &= val - 1;
    }

    // Return the number of differing bits
    return dist;
}

この問題を解決する最善の方法は何ですか?

4

2 に答える 2

3

ビット位置を別々に考えることができます。これにより、32 (またはその他の数) のより簡単な問題が得られます。ここでは、ハミング距離のすべてのペアの合計を計算する必要がありますが、1 ビットの数値を超えていることを除きます。

2 つの 1 ビット数値間のハミング距離は、それらの XOR です。

そして今、この問題の最も簡単なケースになりました - それはすでにビットごとに分割されています.

その質問に対する答えを繰り返すと、ビット位置を取り、0 の数と 1 の数を数え、それらを乗算して、このビット位置の寄与を取得します。すべてのビット位置についてそれらを合計します。この問題ではすべてのビットの寄与の重みが 1 であるため、リンクされた問題よりもさらに単純です。

于 2015-01-22T19:19:11.703 に答える