11

汉明距离:

例如,两个二进制数: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;
}
4

2 回答 2

19

该指令将为您提供一个数字,其中设置了从 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 算法

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

于 2014-03-18T12:38:35.447 回答
0

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

例如 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;
}
于 2018-05-22T06:19:46.440 回答