剑指 Offer 65. 不用加减乘除做加法（位运算、递归、迭代）

一、题目

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

1. 题目描述

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

示例1：

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

示例2：

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

二、分析

这道题不能用加减乘除来做，那么只能用位运算了。我们先考虑a和b为一位二进制数，通过查看a+b来找规律，表格如下：

所以可以得到：
$$\begin{gathered} sum=a⨁b \\ carry=a\&b \end{gathered}$$
因此
$$a+b=sum+(carry<<1)=a⨁b+((a\&b)<<1)(1)$$
注意这里carry要左移一位，计算机内部最高位为符号位。carry左移1位让它变成符号位。

将a+b转换成$a bigoplus b +((a&b)<<1) $后，中间还是有$+$号，因此需要继续通过等式(1)转换，直到b等于0，才能得到结果是a（a+b如果b等于0，那么结果就是a，相当于b一旦等于0，就可以消除加号了）

期望在不断转换过程中b等于0，我们可以用递归方法和迭代来做。

有了这个规律后，将其推广至任意位数的a和b都可。所以，能够推出公式（1）为此题核心。

方法1递归

此方法思路简单，直接看下文代码即可理解。

方法2迭代

设置sum和carry变量，利用公式进行不断进行更新迭代，直到carry等于0，结果就是sum。此方法思路简单，直接看下文代码即可理解。

三、代码

方法1递归

	/*
* 题目：面试题65. 不用加减乘除做加法
* 描述：
* 实现:位运算+递归。1.通过sum=a^b
carry=（a & b）<<1
*
2.a+b转换为sum+carry 因为不能用加号，所以sum+carry 再次经过步骤1，可以用递归实现，递归出口当carry=0,直接返回结果sum
* 复杂度：时间O(1):最差情况下（例如 a =a= 0x7fffffff , b = 1时），需循环 32 次，使用 O(32) 时间。
*
空间 O(1)：递归栈有O(32)常数层辅助空间
*/
int add(int a, int b) {
if (b == 0) {
return a;
}
int sum = a ^ b;
int carry = (unsigned int)(a & b) << 1;//加unsigned int只是因为leetcode评测平台不支持负数移位
return add(sum, carry);
}

方法2迭代

	/*
* 题目：面试题65. 不用加减乘除做加法
* 描述：
* 实现:位运算+迭代。1.通过sum=a^b
carry=（a & b）<<1
*
2.a+b转换为sum+carry 因为不能用加号，所以sum+carry 再次经过步骤1迭代。知道carry等于0，结果就是sum。（a+b=sum+0）
* 复杂度：时间O(1): 最差情况下（例如 a =a= 0x7fffffff , b = 1时），需循环 32 次，使用 O(32) 时间。
*
空间 O(1)：常数辅助空间
*/
int addA(int a, int b) {
int sum, carry;
while (b!=0)
{
sum = a ^ b;
carry = (unsigned int)(a & b) << 1;//加unsigned int只是因为leetcode评测平台不支持负数移位
b = carry;
a = sum;
}
return a;
}

四、总结

这道题需要记住的是加法运算如何转换为位运算。两个要点

• 通过真值表找规律（有点数字信号真值表找表达式的意思）
• 找到表达式之后还是有加号，想办法把加号继续去掉。此题采用的递归。就是不断重复该转换方法。

最后

以上就是难过康乃馨为你收集整理的剑指 Offer 65. 不用加减乘除做加法（位运算、递归、迭代）的全部内容，希望文章能够帮你解决剑指 Offer 65. 不用加减乘除做加法（位运算、递归、迭代）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。