Source
Determine the number of bits required to convert integer A to integer B Example Given n = 31, m = 14,return 2 (31)10=(11111)2 (14)10=(01110)2
题解
比较两个数不同的比特位个数，显然容易想到可以使用异或处理两个整数，相同的位上为0，不同的位上为1，故接下来只需将异或后1的个数求出即可。容易想到的方法是移位后和1按位与得到最低位的结果，使用计数器记录这一结果，直至最后操作数为0时返回最终值。这种方法需要遍历元素的每一位，有咩有更为高效的做法呢？还记得之前做过的 O1 Check Power of 2 吗？x & (x - 1)既然可以检查2的整数次幂，那么如何才能进一步得到所有1的个数呢？——将异或得到的数分拆为若干个2的整数次幂，计算得到有多少个2的整数次幂即可。
以上的分析过程对于正数来说是毫无问题的，但问题就在于如果出现了负数如何破？不确定的时候就来个实例测测看，以-2为例，(-2) & (-2 – 1)的计算如下所示(简单起见这里以8位为准)：
11111110 <==> -2 -2 <==> 11111110 + & 11111111 <==> -1 -3 <==> 11111101 = = 11111101 11111100
细心的你也许发现了对于负数来说，其表现也是我们需要的——x & (x - 1)的含义即为将二进制比特位的值为1的最低位置零。逐步迭代直至最终值为0时返回。
C++
class Solution { public: /** [email protected] a, b: Two integer *return: An integer */ int bitSwapRequired(int a, int b) { int count = 0; int a_xor_b = a ^ b; while (a_xor_b != 0) { ++count; a_xor_b &= (a_xor_b - 1); } return count; } };
Java
class Solution { /** *@param a, b: Two integer *return: An integer */ public static int bitSwapRequired(int a, int b) { int count = 0; int a_xor_b = a ^ b; while (a_xor_b != 0) { ++count; a_xor_b &= (a_xor_b - 1); } return count; } };
源码分析
考虑到负数的可能，C/C++, Java 中循环终止条件为a_xor_b != 0，而不是a_xor_b > 0.
复杂度分析
取决于异或后数中1的个数，O(max(ones in a ^ b)).
关于 Python 中位运算的一些坑总结在参考链接中。
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/20646.html