c++ - 2 つの short int のハミング距離を数える方法は?

Question

ハミング距離:

たとえば、2 つの 2 進数: 1011 と 1000 の HD (ハミング距離) は 2 です。

10000 と 01111 の HD は 5 です。

コードは次のとおりです。

誰かが私にそれを説明できますか？

ありがとう！

short HammingDist(short x, short y)
{
  short dist = 0;
  char val = x^y;// what's the meaning?
  while(val)
  {
    ++dist; 
    val &= val - 1; // why?
  }
  return dist;
}

Answer 1

この命令は、x から y までのすべてのビットが設定された数値を返します。

char val = x^y;

例 ：0b101 ^ 0b011 = 0b110

val同じタイプのオペランド (別名 a ) を持つ必要があることに注意してくださいshort。shortここでは、 aを aにダウンキャストしていてchar、情報が失われています。

以下は、数値に設定されたビット数をカウントするために使用されるアルゴリズムです。

short dist = 0;
while(val)
{
  ++dist; 
  val &= val - 1; // why?
}

これは、 Brian Kernighan アルゴリズムとして知られています。

最後に、コード全体が異なるビットをカウントします。これがハミング距離です。