将整数A转换为B

题目

如果要将整数A转换为B,需要改变多少个bit位?http://www.lintcode.com/zh-cn/problem/flip-bits/

分析

乍看是一道很简单的题目,将两个数进行异或操作,然后计算出为1的比特位个数,就是需要改变的位数,于是有了下面的代码

 public int bitSwapRequired(int a, int b) {
        int r = a ^ b;
        int total = 0;
        
        if(r < 0){
          r = -r;
          total += 1;
        }
        
        while(r > 0){
            total += (r&0x01);
            r = r>>1;
        }
        
        return total;
        
    }

意外的是,这段代码提交后,并没有完全通过测试数据:当 a = 1 , b = -1时,结果不对,标准答案应该是31位, 这时才恍然发现,忽略了负数的特殊表示情形:负数都是使用补码形式进行存储!

简单举例,对于十进制的数,1和-1,其二进制的原码表示应当为(为了示意,这里去4个比特位)
1: 0001b
-1: 1001b

对于这两个数的原码表示形式,只需要符号位发生变化,然而,负数其实并非按照原码的形式存储的,而是补码,负数的补码,是其反码 + 1得到的;正数的补码、反码则仍与原码保持一致。

负数的反码计算,是将除符号位的其他比特位取反得到。仍然拿-1举例,其反码为1110b,因此,-1的补码应当为1111b

注意到这一点,就能立马发现,如果a、b的异或结果为负数时,不能简单的通过负号来消除其符号为上的1,因为当符号位为1时,系统会认为这是一个负数的补码表示。所以,需要进行位运算将符号位特殊处理。

代码

 public int bitSwapRequired(int a, int b) {
        int r = a ^ b;
        int total = 0;
        if(r < 0){
            r = r & 0x7FFFFFFF;
            total++;
        }
        
        while(r > 0){
            total += (r&0x01);
            r = r>>1;
        }
        
        return total;
        
    }
Show Comments

Get the latest posts delivered right to your inbox.