一、题目

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

  1. 题目描述

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

示例1：

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

示例2：

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

二、分析

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

a b sum carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

所以可以得到：
$$
sum=a \bigoplus b\
carry=a&b
$$
因此
$$
a+b=sum+(carry<<1)=a \bigoplus 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递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
* 题目：面试题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迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* 题目：面试题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;
	}

四、总结

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

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