c++ - 如何计算两个短整数的汉明距离？

Question

汉明距离：

例如，两个二进制数：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）。在这里，您将 a 向下转换short为 a char，从而丢失信息。

以下是用于计算数字中设置的位数的算法：

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

它被称为Brian Kernighan 算法。

所以最后，整个代码计算不同的位，这就是汉明距离。

Answer 2

汉明距离是两个数字之间的距离，但计算如下：

例如 2(010) 和 4(100) 之间的距离。现在我们要计算彼此不同的位，因为它需要 xor（xor 计算不同的位）。

取 2 和 4 的 XOR 等于 6(110) 并计算 6 中的设置位等于 2，因此 2 和 4 之间的汉明距离为 2。

在您的代码中：

short HammingDist(short x, short y)
{
  short dist = 0;
  char val = x^y;// calculate differ bit
  while(val)   //this dist veriable calculate set bit in loop
  {
    ++dist; 
    val &= val - 1; 
  }
  return dist;
}