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

摘要

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

一、位运算

有符号整数通常用补码来表示和存储，补码具有如下特征：

• 正整数的补码与原码相同；负整数的补码为其原码除符号位外的所有位取反后加 11。
• 可以将减法运算转化为补码的加法运算来实现。
• 符号位与数值位可以一起参与运算。

思路和算法：虽然题目只要求了不能使用运算符+、-、*和/，但是原则上来说也不宜使用类似的运算符+=、-=、*=和/=，以及sum等方法。于是，我们使用位运算来处理这个问题。首先，考虑两个二进制位相加的四种情况如下：

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 (进位)

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

• 在不考虑进位的情况下，其无进位加法结果为 a⊕b。
• 而所有需要进位的位为a&b，进位后的进位结果为 (a & b) << 1。

于是，我们可以将整数a和 b的和，拆分为a和b的无进位加法结果与进位结果的和。因为每一次拆分都可以让需要进位的最低位至少左移一位，又因为a和 b可以取到负数，所以我们最多需要 log⁡(max_int)次拆分即可完成运算。因为有符号整数用补码来表示，所以以上算法也可以推广到0 和负数。

class Solution {public int add(int a, int b) {while (b != 0) {int carry = (a & b) << 1;a = a ^ b;b = carry;}return a;}
}

复杂度分析

• 时间复杂度：O(log⁡(max_int))，其中我们将执行位运算视作原子操作。
• 空间复杂度：O(1)。

博文参考