题目描述

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

示例:

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

提示：

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

来源：力扣（LeetCode）

题解

位运算

两个二进制位相加的四种情况如下：

1
2
3
4
0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10 (进位)

可以发现，对于整数 a 和 b：

在不考虑进位的情况下，其无进位加法结果为 a ⊕ b。

而所有需要进位的位为 a & b，进位后的进位结果为 (a & b) << 1。

于是，我们可以将整数 a 和 b 的和，拆分为 a 和 b 的 无进位加法 结果与 进位 结果的和。因为每一次拆分都可以让需要进位的最低位至少左移一位，又因为 a 和 b 可以取到负数，所以我们最多需要 n 次拆分即可完成运算，其中 n 是整型的二进制位数，n = 32。

因为有符号整数用补码来表示，所以以上算法也可以推广到 0 和 负数。

AddingWithoutAdditionSubtractionMultiplicationAndDivision

1
2
3
4
5
6
7
8
9
10
11
12
public int add(int a, int b) {
    while (b != 0) {
        // 进位结果 如果进位结果不为 0, 下一次进入循环的时候, 通过无进位加法将结果相加到最终结果中
        // 当进位结果为 0 的时候, 证明已经完成计算
        // 这种方式就是不断地将进位结果加到无进位加法的结果中
        int t = (a & b) << 1;
        // 无进位加法 
        a = a ^ b;
        b = t;
    }
    return a;
}
  • 时间复杂度： O(n) ，其中 n 是整型的二进制位数，n = 32
  • 空间复杂度： O(1)

submissions-2022090901

参考资料

__END__