How to count the hamming distance of two short int?

Question

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

Algol

^ is a bitwise XOR en.wikipedia.org/wiki/Exclusive_or & is bitwise AND – Neolith

on wikipedia en.wikipedia.org/wiki/Hamming_distance where you probably get this code there is an explanation – Shearer

What I'd like to know is how does asking this as an interview question tell you anything about the skills of the candidate beyond whether or not they've been asked this question on an interview before, googled it, and memorized the answer?! How often do you need to find the Hamming Distance in production code? or even use an XOR for that matter? – Cob

Answer 1

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.

Friesian

Answer 2

Hamming distance is a distance between two number but is calculated as below:

For example distance between 2(010) and 4(100). now we want to calculate differ bits from each other for it take xor(xor calculate differ bits).

Take XOR of 2 and 4 which is equal to 6(110) and calculate set bit in 6 which is equal to 2, hence hamming distance between 2 and 4 is 2.

In your code :

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

Slue