首页 > 试题广场 >

整数转化

[编程题]整数转化
  • 热度指数：9348 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

给定两个整数A和B。编写函数，返回将整数A转变成整数B所需要改变的数位个数。

测试样例： 
10,5
返回：4
算法知识视频讲解
添加回答
推荐
XD头像 XD 
思路：A 需要变换 多少位 才能得到B，位变换无非就是0-1,1-0的过程所以，A和B之间 有多少的不同的0-1,1-0的变换就有需要多少位的变换，由于异或操作是 相同为0 不同为1 也即1-0,0-1的结果为1，也就是转换成A^B之后 1 的个数求解；
 
int calcCost(int A, int B) {
        // write code here
        int res = A ^ B;
        int count = 0;
        while(res != 0)
        {
          if((res & 1) !=0)
            {
            	count++;
            }
            res >>= 1;
        }
        return count;
    }

或者：
int calcCost(int A, int B) {
        // write code here
        int res = A ^ B;
        int count = 0;
        while(res != 0)
        {
            count++;
            //去掉最后一位的1 例如 1111 & （1111-1） = 1110 将最后一位1 去掉
            res &= (res-1);
        }
        return count;
    }

编辑于 2015-08-18 19:44:00 回复(3)
更多回答
剑指offer->offer头像 剑指offer->offer 
首先A转化B要改变多少位，即A和B有多少位不同，异或相同则为0，不同为1，接下来就是求一个数的二进制中的1的个数，剑指offer原题
class Transform {
public:
    int calcCost(int A, int B) 
    {
        int num=A^B;
        int count=0;
        while(num)
        {
            count++;
            num=num&(num-1);
        }
        return count++;
    }
};

发表于 2016-07-09 09:31:45 回复(0)
胜文头像 胜文 
import java.util.*;
public class Transform {
    public int calcCost(int A, int B) {
        A ^= B;
            //A和B异或运算后，统计结果中1的个数
        int cnt=0;
        while(A>0){
            if((A&1)>0)cnt++;
                  //A的最后一位是1的时候，A和1位与运算结果为1
            A>>=1;
        }
        return cnt;
    }
}


发表于 2019-06-03 18:11:19 回复(0)
Python
华科平凡头像 华科平凡

python三行解法：

# -*- coding:utf-8 -*-
class Transform:
    def calcCost(self, A, B):
        A=bin(A).replace("0b","").rjust(32,"0")
        B=bin(B).replace("0b","").rjust(32,"0")
        return sum(map(lambda c:A[c]!=B[c],range(32)))

一行解法：

return sum(map(lambda c:bin(A).replace("0b","").rjust(32,"0")[c]!=bin(B).replace("0b","").rjust(32,"0")[c],range(32)))
发表于 2017-10-16 12:07:15 回复(2)
Java
村长，那人偷牛！头像 村长，那人偷牛！ 
//方法一：就是喜欢这么暴力
public int calcCost(int A, int B) {
       int n=A^B,count=0;
       while(n!=0){
            n=n&n-1;//把最右面一个1给他置零
            count++;
       }
       return count;
    }
//方法二：
public int calcCost(int A, int B) {
       int n=A^B,count=0,index=1;;
       while(index!=0){
            count+=(index&n)==0?0:1;
            index<<=1;
       }
       return count;
    }

编辑于 2017-05-14 00:30:21 回复(7)
Aurora1头像 Aurora1 
    public int calcCost(int A, int B) {
		int k = A ^ B, i = 0;
		for (; k != 0; k &= k - 1, i++);
		return i;
	}

编辑于 2016-04-09 13:10:33 回复(0)
L0L头像 L0L 
class Transform {
public:
    int calcCost(int A, int B) {
    	return countone(A^B);
    }
private:
	int countone(int n){
		int count=0;
		while(n){
			++count;
			n&=n-1;
		}
		return count;
	} 
};

发表于 2015-10-03 10:37:54 回复(0)
Java
pein531头像 pein531
统计两个数异或完后有多少个1即可 
import java.util.*;

public class Transform {
    public int calcCost(int A, int B) {
        // write code here
        int xor = A ^ B;
        int count = 0;
        while(xor != 0){
            xor &= xor - 1;
            count ++;
        }
        return count;
    }
}

发表于 2021-11-25 22:45:20 回复(0)
xdtand头像 xdtand
Integer.bitCount((A|B)-(A&B));
发表于 2020-12-01 16:50:46 回复(0)
Simms头像 Simms
异或求 1的个数 
    public int calcCost(int A, int B) {
        // write code here
        int result = A ^ B;
        String binR = Integer.toBinaryString(result);
        String str = binR.replace("1", "");
        return binR.length() - str.length();
    }


发表于 2020-07-08 11:10:01 回复(0)
木然猫猫头像 木然猫猫

Python一行 

# -*- coding:utf-8 -*-
class Transform:
    def calcCost(self, A, B):
        return bin(A ^ B).count('1')
编辑于 2018-12-27 09:44:11 回复(0)
晴雯晴雯头像 晴雯晴雯 
// 不利用额外空间
int calcCost(int A, int B) {
    // write code here
    // 异或计算需要多少个1
    A=A^B;
    // 用B来计数
    B=0;
    // 常用的计算1个数的算法，大家可以记住
    while(A){
        B++;
        A=A&(A-1);
        }
    return B;
}

发表于 2018-11-16 15:43:29 回复(0)
Python
JaynvChen头像 JaynvChen 
# 返回A^B后的二进制字符串中“1”的个数
return bin(A ^ B).count('1')

发表于 2018-01-09 14:10:26 回复(0)
InGodWeTrust头像 InGodWeTrust 
import java.util.*;
//直接用Integer内置的bitCount来计算二进制里1的个数
public class Transform {
    public int calcCost(int A, int B) {
		int sum=A^B;
		return Integer.bitCount(sum);
    }
}
参考：http://blog.csdn.net/sinat_22797429/article/details/75451808
编辑于 2017-07-25 22:24:00 回复(0)
maoxiaomi头像 maoxiaomi 
 public int calcCost(int A, int B) {
        // write code here
        int x= A^B;
        String s=Integer.toBinaryString(x);
        int count=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='1')count++;
        }
        return count;
    }

发表于 2017-05-01 10:13:12 回复(0)
Java
噢买够头像 噢买够 
public int calcCost(int A, int B) {
	int d = A ^ B;
	int count = 0;
	while (d > 0) {
		int power2 = 1;
		while (power2 << 1 <= d) 
			power2 <<= 1;
		d -= power2;
		count++;
	}
	return count;
}
大家写的都是用n&(n-1)去掉最后一位1的，学到了。贴一个自己写的简陋版本，不断减去最大的2的倍数
编辑于 2016-11-20 16:22:51 回复(0)
Java
砚南头像 砚南 
 public  int calcCost(int A, int B) {
        // write code here
    	int r=0;
    	int result=A^B;
    	String resultToString=Integer.toBinaryString(result);
    	System.out.println(resultToString);
    	for(char c:resultToString.toCharArray()){
    		if(c=='1'){
    			r++;
    		}
    	}
		return r;
    }

发表于 2016-09-26 16:44:31 回复(0)
Java
linklist头像 linklist
public class Transform {
    public int calcCost(int A, int B) {
        // temp中为1的位就是AB不同的位，接下来求temp1的个数就可以
        int temp = A ^ B;
        int count = 0;
        while (temp != 0) {
            temp &= (temp - 1);
            count++;
        }
        return count;
    }
}
发表于 2016-09-21 12:45:47 回复(0)
Ron头像 Ron 
/*
	 * 思路：比较A和B每位上数字是否相同，使用异或方式比较
	 * 获取每位数字的方法：A-(A >>> 1 << 1)，A无符号右移1位再左移一位，原数A减去该数，得到最低位的值
	 * 循环内进行异或比较后，将A >>> 1，因为最低位已比较完毕，故到较高一位比较
	 */
	public int calcCost(int A, int B) {
		// write code here
		int res = 0;
		while(A != 0 || B != 0){
			int Abit = A - (A >>> 1 << 1);
			int Bbit = B - (B >>> 1 << 1) ;
			if((Abit ^ Bbit) == 1){
				res++;
			}
			A = A >>> 1;
			B = B >>> 1;
		}
		return res;
	}

发表于 2015-10-19 11:04:56 回复(0)
yr123头像 yr123

public int calcCost(int A, int B) {

//异或运算

int temp=A^B;

//判断有多少个1

int  count=0;

while(temp!=0){

count++;

temp=temp&(temp-1);

}

        return count;

    }

发表于 2015-10-06 23:40:18 回复(0)
递归头像 递归
class Tran敏感词orm {
public:
    int calcCost(int A, int B) {
        bitset<32> bit= A^B;    //求相异的位  标记为1
    return bit.count();
    }
};
发表于 2015-08-10 15:57:18 回复(0)
提交观点

问题信息

模拟
难度：
99条回答 11837浏览

热门推荐

通过挑战的用户

查看代码

相关试题

整数转化

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号