(lintcode)第1题 A+B问题

给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符

说明

a和b都是 32位 整数么?是的

我可以使用位运算符么?当然可以

样例

如果 a=1 并且 b=2,返回3

 

由于不可以使用加号,那么我们只能考虑使用位运算和二进制来计算,首先假如要计算7+17,那么我们看7的二进制表示为111,17的二进制表示为10001

第一步:忽略掉进位来相加,就是0+0=0,0+1=1,1+0=1,1+1=0;

第二步:我们要知道哪一位进了位,那么只要使用&操作即可,例如1&1=1,而进位则是10=(1&1)<<1,把与操作的结果向左移动了一位

第三步:把不进位操作的结果,也就是第一步的结果和进位操作的结果(第二步的结果)进行相加即可。

到这里肯定有个疑问,那就是第三步中相加要是还有进位怎么办?这就要我们去联想到递归了,也就是不断地重复上面的两步,直到不再产生进位。

代码如下:

 

public class Solution {
    /*
     * @param a: An integer
     * @param b: An integer
     * @return: The sum of a and b
     */
    public int aplusb(int a, int b) {  
        // write your code here, try to do it without arithmetic operators.  
        if(a==0) return b;  //不再进位
        if(b==0) return a;  //不进位操作为零,直接取进位操作的结果
        int sum,i;  
        i=a^b; //不进位相加的结果 
        sum=(a&b)<<1;  //进位的结果
        return aplusb(sum,i); // 两者再进行相加
    }  
}

如果有所帮助,脸皮厚求个赞~

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

技术之路不在一时,山高水长,纵使缓慢,驰而不息。

公众号:秦怀杂货店

 

 

 

 

上一篇:(lintcode)第3题统计数字


下一篇:(lintcode)第2题尾部的零