面试题 17.01.不用加号的加法

1. 题目描述

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:

输入: a = 1, b = 1
输出: 2

提示：

• a , b 均可能是负数或 0
• 结果不会溢出 32 位整数

标签 位运算 数学

2. 解题

• 分析 可以使用位运算。 两个数字转换成二进制，再相加，则就是这两个二进制数的每一位分别对应相加。 二进制只有0和1, 两个二进制位相加分为4种情况:

     0 + 0 =  0 
     0 + 1 =  1 
     1 + 0 =  1 
     1 + 1 = 10 

所以可以得出结论：对于两个数 a,b 若不考虑进位，则相加的结果是

    a ^ b

什么情况下会产生进位？ 即对应的两个数位都为1的时候，即进行 & 运算， 由于是往"更高的一位"进位，所以需要“左移一格”,即 << 1 ; 所以只进位的部分为

    (a & b) << 1

• 递归解法 对于上面的分析,我们可以得出: 两个数 a,b 相加, 即add(a, b), 若相加时没产生进位, 即(a & b) << 1为零，那么 add(a,b) = a ^ b; 如果(a & b) << 1大于零，说明相加时有进位,那么必须把进位给"补上", 即 (a ^ b) + ((a & b) << 1), 那么此刻又转换到了 两个数 (a ^ b) 和 ((a & b) << 1) 相加，即add(a ^ b, (a & b) << 1), 出现了递归关系, 一直递归到两数相加不发生进位时, 递归出口是当 (a & b) << 1 == 0 时, 即 add(int num1, int num2)当第二个入参num2==0时。