Convert Integer A to Integer B详解编程语言

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

(0)
上一篇 2021年7月19日 23:36
下一篇 2021年7月19日 23:36

相关推荐

发表回复

登录后才能评论