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/tech/pnotes/20646.html