⭐️剑指 Offer 65. 不用加减乘除做加法⭐️

🔐题目详情

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

示例：

输入: a = 1, b = 1输出: 2输入: a = 5, b = 6输出: 11

提示：

1. a, b 均可能是负数或 0。

2. 结果不会溢出 32 位整数。

💡解题思路

方法 1：你说不能使用加减乘除运算符？我偏要用，直接将两数相加返回。

方法 2：位运算。

预备知识：

• [x] 按位与 & ：双目运算符，对每位取与，都为 1 则为 1，否则为 0。

• [x] 按位异或 ^ ：双目运算符，对每位取异或，对应位两数不相同为 1，否则为 0。

• [x] 左移 << ：双目运算符，a << b ，表示将 a 的二进制位左移 b 位，最右边补 0。

• [x] 加法进位的特点：对于二进制，发生进位的条件是两个数所对应的二进制位均为 1。

解题思路：

实现 a，b 两数完整加法的步骤：

1. 将 a 与 b 按位与并左移一位，即(a & b) << 1，不妨将此结果存至变量 tmp，若此数值为 0，就表示两数未发生进位。

2. 将 a 与 b 进行非进位加法，即 a ^ b，不妨将此结果赋值给 a，将上面所得 tmp 值赋值给 b。

3. 此时 b 的值为 tmp，判断 b 是否为 0，若 b 不为 0，需要进位，重复上述步骤，将进位数 b 与前一次非进位加法的值非进位相加，若 b 为 0，不需要进位，加法过程结束，最终结果即 a 的值。

注意：C/C++对负数左移存在溢出，先将 a & b 强转为 unsigned int 以保护左移溢出的情况！

🔑源代码

Java:

class Solution {    public int getSum(int a, int b) {        //两数异或相当于不进位相加，两数按位与运算能够得到需要进位的数，将此数左移再异或相加，直到该数为0，加法计算完毕        while (b != 0) {            int tmp = (a & b) << 1;            a ^= b;            b = tmp;        }        return a;    }}

C:

int getSum(int a, int b){    while (b) {        int tmp = (unsigned int)(a & b) << 1;//C/C++，负数情况，对有符号数左移存在溢出，先转无符号再左移对溢出情况保护处理        a ^= b;        b = tmp;    }    return a;}

C++:

class Solution {public:    int getSum(int a, int b) {        while (b) {            int tmp = (unsigned int)(a & b) << 1;            a ^= b;            b = tmp;        }        return a;    }};

🌱总结

不用加减乘除做加法，最容易想到的方法就是位运算，通过了解各种位运算的特点，找出模拟加法的适当方法。力扣同源题：371. 两整数之和面试题 17.01. 不用加号的加法力扣类似题：面试题 08.05. 递归乘法29. 两数相除50. Pow(x, n)69. Sqrt(x)面试题 16.07. 最大数值