Search code examples
c++shorthamming-distancecensus

How to count the hamming distance of two short int?

Hamming Distance:

For example, two binary number: 1011 and 1000's HD(Hamming distance) is 2.

The 10000 and 01111's HD is 5.

Here is the code:

Can some one explain it to me?

Thanks!

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;
}
Solution

  • This instruction will give you a number with all bits that differs from x to y are set : 

    char val = x^y;

    Example : 0b101 ^ 0b011 = 0b110

    Notice that val should have the same type of the operands (aka a short). Here, you are downcasting a short to a char, loosing information.

    The following is an algorithm used to count the number of bits set in a number :

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

    It is known as the Brian Kernighan algorithm.

    So finally, the whole code counts bits that differs, which is the hamming distance.