Transform one integer to another

Question

Suppose there are given two integers, a and b, and we know that a>b. I want to calculate how many operations I should make on b to get a (by operation I mean that bitwise operations change a bit from 1 to 0 and vice versa. How can I count the number of operation for such a transform?

Answer 1

That would be the population count (number of 1 bits) in a XOR b.

Answer 2

You are looking for the Hamming distance. This is the number of bits in which the two numbers differ, which gives you the number of bits you need to change in order to make one number into the other.

Answer 3

What you are looking is called the Hamming distance. Here is how I compute it in C/C++:

unsigned hamdist(unsigned x, unsigned y)
{
  unsigned dist = 0;
  unsigned val = x ^ y;

  // Count the number of set bits (Knuth's algorithm)
  while(val)
  {
    ++dist;
    val &= val - 1;
  }
  return dist;
}