Interview question: Number of bit swaps required to convert one integer to another

A friend of mine was asked this question in an interview. I wasn't able to figure out a solution to this. Question -

Write a function to cal开发者_StackOverflow中文版culate the number of bit swaps required to convert one integer to other.

The bit operation which can be used to figure out which bits are different is xor. Each 1 in the xor value will tell the different bit between the two integers.

int getBitSwapCount(int x, int y) {
    int count = 0;
    for(int z = x^y; z!=0; z = z>> 1) {
        count += z & 1;
    }
    return count; 
}

Interview questions aren't only about solutions, they're also (and this is generally even more important that finding a solution) giving you the opportunity to show how you would tackle a novel problem such as this. How would you start on this ? Is there any further information you'd like to know to help you solve it ? Are there any standard functions (in any commonly-used programming language) you'd like to use ?

Give us your best shot, we'll play the interviewer(s) and prompt as you go ...

XOR the values and then count the number of ones in the result

I fail to see anything special about this question. Iterating over the bits of both integers, combining the current bits via XOR and incrementing a counter if the result is not equal to zero will give you the number of bits that differ in both values.

Different approach

find and the binary string and calculate Levenshtein distance by dynamic programming

Take the XOR of 2 numbers (say a & b), and count the number of ones in the a^b

int bitsSwapRequired (int a, int b){
    int count = 0;
    for (int c = a ^ b; c!=0 ; c >> 1)
        count += c & 1;
    return count;
}

We can make it a bit better, rather than simply shifting c repeatedly while checking the least significant bit, we can continuously flip the rightmost bit set to 1 and count how long it takes c to reach 0. The operation c = c & (c-1) will clear the rightmost bit set to 1 in c.

int bitsSwapRequired (int a, int b){
    int count = 0;
    for (int c = a ^ b; c != 0; c = c & (c-1))
        count ++;
    return count;
}