1 A+B问题

原题网址： http://www.lintcode.com/zh-cn/problem/a-b-problem/#

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

注意事项

你不需要从输入流读入数据，只需要根据aplusb的两个参数a和b，计算他们的和并返回就行。

您在真实的面试中是否遇到过这个题？

Yes

说明

a和b都是 32位 整数么？

是的

我可以使用位运算符么？

当然可以

样例

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

挑战

显然你可以直接 return a + b，但是你是否可以挑战一下不这样做？

标签

比特位操作 Cracking The Coding Interview

方法：使用位运算。哇的一声哭出来，没用过位运算的我完全懵逼，还是基础太差。

参考：https://blog.csdn.net/cjt5047/article/details/50686724

具体思路上面的链接已经说的很清楚了，加法的步骤：

1、忽略进位对位数字相加

2、记录进位

3、进位值与第一步结果相加。

考虑二进制数的情况（5＝101，17＝10001）：
仍然分3步：
    1. 忽略进位，对应各位数字相加，得到10100；
    2. 记录进位，本例中只有最后一位相加时产生进位1，进位值为10（二进制）；
    3. 按照第1步中的方法将进位值与第1步结果相加，得到最终结果10110，正好是十进制数22的二进制表示。

接下来把上述二进制加法3步计算法用位运算替换：
    第1步（忽略进位）：0＋0＝0，0＋1＝1，1＋0＝0，1＋1＝0，典型的异或运算。
    第2步：很明显，只有1＋1会向前产生进位1，相对于这一数位的进位值为10，而10＝(1&1)<<1。
    第3步：将第1步和第2步得到的结果相加，其实又是在重复这2步，直到不再产生进位为止。

（注意相加相当于调用函数自身，只不过参数变成了进位与忽略进位的和）——递归

两种情况：若进位为0，返回第一步相加结果；若进位不为0，进位与第一步的和相加其实是重复上面1、 2、两步，直到进位为0。——循环

PS：再简单说下第2步的理解，两个二进制数a和b相加，只有都是1的数位会产生进位，‘&’——与运算可以找到会产生进位的数位，再将其整体左移1位就可以得到两数相加的进位值了。

递归：

 int aplusb2(int a, int b)

 {

     if (a==)

     {

         return b;

     }

     if (b==)

     {

         return a;

     }

     int x=a^b;

     int y=(a&b)<<;

     return aplusb2(x,y);

 }

循环：

 class Solution {

 public:

     /**

      * @param a: An integer

      * @param b: An integer

      * @return: The sum of a and b

      */

     int aplusb(int a, int b) {

         // write your code here

         while(b!=)

     {

     int x=a^b;

     int y=(a&b)<<;

     a=x;

     b=y;

     }

     return a;

     }

 };

其他参考：

https://blog.csdn.net/aphysia/article/details/77507919

https://www.cnblogs.com/whaochen205/p/5832758.html

巴特西

1 A+B问题

注意事项

最新文章

热门文章