Question from the interview: the number of bit swaps needed to convert one integer to another

Question

My friend was asked this question in an interview. I could not find a solution to this. Question -

Write a function to calculate the number of bit swaps needed to convert one integer to another.

Answer 1

The bit operation, which can be used to determine which bits are different, is xor.

Each 1 in xor will indicate a bit between 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; 

}

Answer 2

Interview questions are not only about solutions, but also (and it is usually even more important to find a solution), giving you the opportunity to show how you will solve a new problem, such as this. How would you start with this? Is there any additional information you would like to know to help you solve it? Are there standard features (in any commonly used programming language) that you would like to use?

Give us your best shot, we will play an interviewer and tell me how you are going ...

Answer 3

XOR values, and then count the number of units in the results

Answer 4

I do not see anything special in this matter. Iterating over the bits of both integers, combining the current bits through XOR and increasing the counter, if the result is not zero, you will get the number of bits that are different from each other.

Answer 5

Different approach

find and binary string and calculate Levenshtein distance by dynamic programming

Answer 6

Take an XOR of two numbers (say a and b) and count the number of units in ^ 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 do this a little better than just flipping c repeatedly, checking the least significant bit, we can continuously flip the right-most bit set to 1 and calculate how long it takes c to reach 0. Operation c = c and (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; }