lintcode:Flip Bits 将整数A转换为B

题目:

如果要将整数A转换为B,需要改变多少个bit位?

样例

如把31转换为14,需要改变2个bit位。

()10=()2

()10=()2

挑战

你能想出几种方法?

解题:

A-->B二进制要变化多少位?就是考虑A、B对应的二进制数有多少不同的,A、B的异或结果中出现的1的个数就是需要改变的比特位

问题转换成,10进制的数中,二进制表示情况下1的个数,这个题目之前求过,编程之美上面也有的。

上面的方法1不可取,因为这里的数据有负数。

其他两种方法如下:

Java程序:

利用位运算:

class Solution {
/**
*@param a, b: Two integer
*return: An integer
*/
public static int bitSwapRequired(int a, int b) {
// write your code here
int c = a^b;
int count = 0;
while(c!=0){
count += c&1;
c=c>>>1;
}
return count;
}
};

总耗时: 2834 ms

利用位运算 与减法

class Solution {
/**
*@param a, b: Two integer
*return: An integer
*/
public static int bitSwapRequired(int a, int b) {
// write your code here
int c = a^b;
int count = 0;
while(c!=0){
c = c&(c-1);
count++;
}
return count;
}
};

总耗时: 2366 ms

取一位判断一位:

class Solution {
/**
*@param a, b: Two integer
*return: An integer
*/
public static int bitSwapRequired(int a, int b) {
// write your code here
int count=0;
while(a!=0 || b!=0){
int ai = a&1;
int bi = b&1;
if(ai==1 && bi==0 || ai==0 && bi==1)
count++;
a = a>>>1;
b = b>>>1;
}
return count;
}
};

总耗时: 2103 ms

Python程序:

直接转换成python时间超时。。。

上一篇:IIS启用.net2.0


下一篇:Maven的下载和配置