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

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).在这里,你正在向下传播shorta char,丢失信息.

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

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

它被称为Brian Kernighan算法.

最后,整个代码计算不同的位,即汉明距离.