Bits needed to change one number to another

Question

Say I have two positive numbers a and b. How many bits must be inverted in order to convert a into b ? I just want the count and not the exact position of the differing bits.

Lets assume a = 10 ( 1010 ) and b = 8 ( 1000 ). In this case the number of bits that should be inverted equals 1.

Any generalised algorithm?

Answer 1

The solution is simple

• Step 1 ) Compute a XOR b
  
• Step 2 ) Count the number of set bits in the result

Done!

Answer 2

int a = 10;
int b = 8;

int c = a ^ b; //xor
int count = 0;
while (c != 0)
{
  if ((c & 1) != 0)
    count++;
  c = c >> 1;
}
return count;

Answer 3

changeMask = a XOR b
bitsToChange = 0
while changeMask>0
  bitsToChange = bitsToChange + (changeMask AND 1)
  changeMask = changeMask >> 1
loop
return bitsToChange

Answer 4

Good old-fashioned bit operations!

size_t countbits( unsigned int n )
{
   size_t bits = 0;
   while( n )
   {
      bits += n&1;
      n >>= 1;
   }
   return bits;
}

countbits( a ^ b );

This could would work in C as well as C++. You could (in C++ only) make the countbits function a template.