Bits needed to change one number to another

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 co开发者_开发百科unt 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?

The solution is simple

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

Done!

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;

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

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.

Actually,humbly building on previous answer - this might work better for converting a to b:

the only difference with previous answer is that the bits already set in b dont need to be set again - so dont count them.

calculate (a XOR b) AND ~b

count the set bits

post corrected as per comment. Thanks!

abs(popcount(a) - popcount(b)) where popcount counts bits set in number (a lot of different variants exists)