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

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

题目详情

写一个函数，求两个整数之和，要求在函数体内不得使用 

四则运算符号。

示例：

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


提示：

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

• 结果不会溢出 32 位整数。

解题思路

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

方法2：位运算。

预备知识：

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

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

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

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

解题思路：

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

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

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

• 此时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. 最大数值