如何计算两个short int的汉明距离？

Question

海明距离：

例如，二进制数1011和1000的海明距离为2。

10000和01111的海明距离为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;
}

- David Ding

---

^ 是按位异或 http://en.wikipedia.org/wiki/Exclusive_or & 是按位与。 - Cory Kramer

在维基百科的http://en.wikipedia.org/wiki/Hamming_distance页面上，您可能会找到此代码的解释。 - sim

我想知道的是，将这个问题作为面试问题是否能告诉你有关候选人技能的任何信息，除了他们是否之前在面试上被问过这个问题、是否搜索过它并记住了答案？生产代码中有多频繁需要找到汉明距离？甚至使用异或吗？ - Christopher Pisz

Answer 1

这个指令将给出一个数字，其中所有与x到y不同的位都被设置为1：

char val = x^y;

例子: 0b101 ^ 0b011 = 0b110

注意到val应该与操作数具有相同的类型（即一个short）。在这里，你将一个short向下转换为一个char，导致信息丢失。

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

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

它被称为Brian Kernighan算法。

因此，整个代码最终计算不同的位数，也称为汉明距离。

- Kiwi

---

谢谢你的回答！ - David Ding

Answer 2

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

例如，2(010)和4(100)之间的距离。现在我们想要计算彼此不同的位数，可以采用异或（XOR）计算不同的位数。

取2和4的异或值，得到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;
}

- Dhavalkumar Prajapati