题目的意思就是,如何判断A和B的二进制表示中有多少位(bit)不一样?
这是编程之美当中一道练习题,我也就邯郸学步的想了一个算法:
1. 先做位与运算 A & B, 得到结果C;
2. 接着做位或运算 A | B,得到结果D;
3. 再做一次异或运算,不过操作的数不是 A 与 B,而是 C ^ D , 得到结果E;
4. 判断结果 E 其二进制表示中1的个数就得到结果啦。
以下举例说明,为了减少复杂度,就使用八位二进制吧。设 A = 0010 1011, B = 0110 0101.
1. C = A & B = 0010 0001;
2. D = A | B = 0110 1111;
3. E = C ^ D = 0100 1110;
4. 结果E中有4个1,那么也就是说将A变成B,需要改变4位(bit)。
至于如何判断E的二进制表示中有几个1,请参考编程之美p33。
算法原理如下:
1. A & B,得到的结果C中的1的位表明了A和B中相同的位都是1的位;
2. A | B, 得到的结果D中的1的位表明了A和B在该位至少有一个为1的位,包含了A 与 B 都是1的位数,
经过前两步的位运算,,C 中1的位表明了A 和 B在该位都是1,D中为0的位表明了A 和 B 在该位都是0 ,所以进行第三步。
3. C ^ D,E 中为1的位表明了A 和 B不同的位。
分享到:
相关推荐
给定一个正整数a,以及另外的5个正整数,问题是:这5个整数中,小于a的整数的和是多少? 输入要求 输入一行,只包括6个小于100的正整数,其中第一个正整数就是a。 输出要求 输出一行,给出一个正整数,是5个数中...
对于给定的2 个正整数a <= b 计算a 和b之间约数个数最多的数。 可以保证a和b都不超过2000000. 数据输入: 输入数据有2个正整数a和b。 结果输出: 若找到的a 和b之间约数个数最多的数是x,将div(x)输出。 Sample ...
求两个正整数a 和 b的最大公约数。要求使用c++ class编写程序。可以创建如下class
给定两个均不超过9的正整数a和n,要求编写程序求a+aa+aaa++⋯+aa⋯a(n个a)之和。
给定两个数A和B(长度不超过100),如果它们相等则输出"YES",否则输出"NO"。 Input 每组测试数据包含两个数A和B。 Output 对于每组测试数据,如果A和B相等,则输出"YES",否则输出"NO"。 Sample Input 1 2 2 2 3 3 ...
给定两个整数A和B,其表示形式是:从个位开始,每三位数用逗号","隔开。 现在请计算A+B的结果,并以正常形式输出。
# 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 # 示例: # 输入: n = 4, k = 2 # 输出: # [ # [2,4], # [3,4], # [2,3], # [1,2], # [1,3], # [1,4], # ]
设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作...
给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X={A,B,C,B,D,B,A},Y={B,D,C,A,B,A},则序列{B,C,A}是X和Y的一个公共子序列,但它不是X和Y的一个...
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
C++,输入两个正整数a和n,求a+aa+aaa+…+aa…a(n个a)之和
实现算法: 给定两个整数u和v,它们分别有m和n位数字,且m≤n。用通常的乘法求uv的值需要O(mn)时间。我们可以将u和v均看作是有n位数字的大整数。用分治法在O(nlog3)时间内计算uv的值。当m时,此法效率不高。...
/*加和*/ //给定一个整数t,以及n个整数,在这n个整数中找到加和为t的所有组合。
第一行为一个整数C,表示有C组测试数据,接下来有2*C行数据,每组测试数据占2行,每组测试数据第一行是1个整数n,表示有n个整数,接下来一行有n个整数,它们之间用空格隔开. Output 你的输出应该有C行,即每组...
任意给定 n 个整数,求这 n 个整数序列的和、最小值、最大值 输入描述 输入一个整数n,代表接下来输入整数个数,n,接着输入n个整数,整数用int表示即可。 输出描述 输出整数序列的和、最小值、最大值。用空格隔开...
2. 给定两个字符串A、B,试输入A和B连接后的字符串; 3. 给定字符串A和整数n、m,求出A的第 n 个和第m个字符之间的子串并输出; 4. 给定两个字符串,判断A和B是否相等; 5. 不能利用已有的系统函数实现上述功能...
给定n 个整数组成的序列,编程计算该序列的最优m 段分割,使m 段子序列的和的最大值达到最小。 Input 输入由多组测试数据组成。 每组测试数据输入的第1行中有2个正整数n和m。正整数n是序列的长度;正整数m是分割...
给定一个整数n,求出所有连续的且和为n正整数。比如对于整数27,结果为2~7、8~10、13和14,因为这些数之间的整数的和都是27。注意:并不是所有的整数都有结果,例如不存在连续的整数和为16。为了提高计算的效率,...
编程任务:对于给定的2 个正整数a≤b,编程计算a 和b 之间约数个数最多的数。 Input 输入数据的第1 行有2 个正整数a和b。 Output 程序运行结束时,若找到的a 和b 之间约数个数最多的数是x,将div(x)输出。
给定两个数X和Y,打印出X和Y采用分治法计算X*Y过程中,拆分的ABCD四个部分的值,和最终的计算结果。 Input 输入为两个整数X,Y Output 采用分治法求解过程中计算的ABCD的值,和最终X*Y的结果 输出结果中间有空格...