面试问题：将一个整数转换为另一个整数所需的位交换次数

Question

我的一个朋友在接受采访时被问到这个问题。我无法找到解决方案。 问题 -

编写一个函数来计算将一个整数转换为另一个整数所需的位交换次数。

Answer 1

可用于找出哪些位不同的位运算是异或。异或值中的每个 1 将告诉两个整数之间的不同位。

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

面试问题不仅与解决方案有关，而且（这通常比寻找解决方案更重要）让您有机会展示如何解决此类新问题。你会如何开始呢？您还想了解更多信息来帮助您解决问题吗？您想使用任何标准函数（在任何常用的编程语言中）吗？

给我们你最好的机会，我们将扮演面试官并在你进行过程中进行提示......

Answer 3

对值进行异或，然后计算结果中的个数

Answer 4

我看不出这个问题有什么特别之处。迭代两个整数的位，通过 XOR 组合当前位并在结果不等于零时递增计数器，将给出两个值中不同的位数。

Answer 5

不同的方法

查找二进制字符串并通过动态规划计算 Levenshtein 距离

Answer 6

对 2 个数字（例如 a 和 b）进行异或，并计算 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;
}

我们可以做得更好一点，而不是简单地在检查最低有效位时重复移动 c，我们可以连续翻转最右边的位设置为 1，并计算 c 达到 0 所需的时间。操作 c = c & (c-1) 将清除 c 中设置为 1 的最右边位。

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