剑指 offer：48、不用加减乘除做加法

48. 不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

解题思路：

题目要求不得使用+、-、*、/四则运算，了解计算机CPU的物理实现或者数字电路的同学应该知道，计算机完成计算是通过门电路（与门、非门、与非门等等）进行二进制运算来实现我们人类认知的所有运算的。我们先观察一下十进制进行运算的过程。这里我们以8+14=22为例：

1. 只做各位相加不进位，此时相加的结果是12（个位数8和4相加不进位是2，十位相加结果是1）
2. 做进位，8+4有进位，进位值为10
3. 将前两步的结果相加：12+10的结果为22，也就是8+14的结果。（重复1、2步骤）

可以看出，十进制进行加法运算时，最终的结果 = 无进位加法 + 进位值。这个结论同样适用于二进制运算，同样以8+14即1000 + 1110为例：

1. 只做各位相加不进位，此时结果为0110
2. 做进位，两者相加进位值为10000
3. 将两步结果相加：0110 + 10000 = 10110转化为十进制为22（重复1、2步骤）

我们来观察一下二进制运算1、2步的结果，0110是1000 ^ 1110的结果，10000是1000 & 1110后左移一位的结果。这样我们只需要重复1、2步骤，直到没有进位为止，便可得到最终结果。

解答：

// 方法1: while循环
class Solution {
public:
    int Add(int num1, int num2)
    {
        // 最终的结果 = 无进位加法 + 进位值
        while (num2 != 0)
        {
            int temp = num1 ^ num2;
            num2 = (num1 & num2) << 1;
            num1 = temp;
        }
        return num1;
    }
};
// 方法2: 递归实现
class Solution {
public:
    int Add(int num1, int num2)
    {
        // 最终的结果 = 无进位加法 + 进位值
        return num2 ? Add(num1 ^ num2, (num1 & num2) << 1) : num1;
    }
};

大家有兴趣可以访问我的个人博客，不定时更新一些内容哦！

图片来自必应壁纸