题目信息

  • 题目：剑指 Offer 65. 不用加减乘除做加法

  • 时间： 2020-08-04

  • 题目链接：Leetcode

  • tag： 位运算 限制运算符号

  • 难易程度：中等

  • 题目描述：

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

示例1:

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

注意

1
2
1. a, b 均可能是负数或 0
2. 结果不会溢出 32 位整数

解题思路

本题难点

求和不使用 “+”、“-”、“*”、“/” 四则运算符号。

具体思路

位运算

设两数字的二进制形式 a,b ，其求和 s=a+b ，a(i) 代表 a 的二进制第 i 位，则分为以下四种情况：

a(i) b(i) 无进位和n(i) 进位和c(i)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

无进位和 与 异或运算 规律相同

进位 和 与运算 规律相同（并需左移一位）

即可将 s = a+b 转化为： s = 非进位和 n + 进位 c

循环求 n和 c ，直至进位 c=0；此时 s=n，返回 n即可。

提示

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int add(int a, int b) {
        int c = 0;
        while(b != 0){
            c = (a & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }
}

复杂度分析：

  • 时间复杂度 O(1) ： 最差情况下（例如 a= 0x7fffffff , b=1 时），需循环 31 次，使用 O(1) 时间；每轮中的常数次位操作使用 O(1) 时间。
  • 空间复杂度 O(1) ： 使用常数大小的额外空间。

其他优秀解答

解题思路

递归法，把a+b转换成非进位和+进位，由于不能用加法，因此要一直转换直到第二个加数变成0。

代码

1
2
3
4
5
6
7
8
9
class Solution {
    public int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        // 转换成非进位和 + 进位
        return add(a ^ b, (a & b) << 1);
    }
}