剑指offer 面面试题65. 不用加减乘除做加法（易）

考查应聘者对二进制和位运算的理解。

Question

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

示例: 

1
2
输入: a = 1, b = 1
输出: 2
提示：a, b 均可能是负数或 0，结果不会溢出 32 位整数。

测试用例

输入正数、负数和0。

本题考点

考查应聘者的发散思维能力。当“+”、“-”、“×”、“/”运算符都不能使用时，应聘者能不能打开思路想到用位运算做加法，是能否顺利解决这个问题的关键。 考查应聘者对二进制和位运算的理解。

Intuition

拆分加法过程 首先我们可以分析人们是如何做十进制加法的，比如是如何得出 5+17=22 这个结果的。实际上，我们可以分成三步进行：
第一步、只做各位相加不进位，此时相加的结果是12（个位数5和7相加不要进位是2，十位数0和1相加结果是1）；
第二步、做进位，5+7中有进位，进位的值是10；
第三步、把前面两个结果加起来，12+10的结果是22，刚好5+17=22。

用位运算替代加法完成上述三个步骤 5的二进制是 101，17的二进制是 10001。我们还是试着把计算分成三步： 第一步、各位相加但不计进位，得到的结果是10100（最后一位两个数都是1，相加的结果是二进制的10。这一步不计进位，因此结果仍然是0）。第一步不考虑进位对每一位相加。0加0、1加1的结果都是0，0加1、1加0的结果都是1，这个过程可以用位异或来替代。 第二步、记下进位，在这个例子中只在最后一位相加时产生一个进位，结果是二进制的10。对0加0、0加1、1加0而言，都不会产生进位，只有1加1时，会向前产生一个进位。此时我们可以想象成两个数先做位与运算，然后再向左移动一位； 第三步、把前两步的结果相加，得到的结果是10110，转换成十进制正好是22。第三步把前两个步骤的结果相加，第三步相加的过程依然是重复前面两步，直到不产生进位为止。

考虑负数问题 Q ： 若数字 aa 和 bb 中有负数，则变成了减法，如何处理？ A ： 在计算机系统中，数值一律用 补码来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。 Python有其特殊性：Python / Java 中的数字都是以补码形式存储的。但 Python 没有 int , long 等不同长度变量，即没有变量位数的概念。 获取负数的补码： 需要将数字与十六进制数 0xffffffff 相与。可理解为舍去此数字 32 位以上的数字，从无限长度变为一个 32 位整数。 返回前数字还原： 已知 0x7fffffff 是最大正数的补码， 0x7fffffff 就是31位全是1的二进制数的16进制形式，若补码 a>0x7fffffff ，则说明 a 为负数。需执行 ~(a ^ 0xffffffff) 操作，将补码还原至 Python 的存储格式。 a ^ 0xffffffff 运算将 1 至 32 位按位取反； ~ 运算是将整个数字取反；因此， ~(a ^ 0xffffffff) 是将 32 位以上的位取反，即由 0 变为 1 ， 1 至 32 位不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>>> a = '0xffffffff'
>>> a
'0xffffffff'
>>> b = int(a, 16)
>>> b
4294967295
>>> hex(1)  # 0x1 补码
'0x1'
>>> hex(-1)  # -0x1 负号 + 原码 （ Python 特色，Java 会直接输出真实补码0xffffffff）
'-0x1'
>>> hex(1 & 0xffffffff)  # 0x1 正数补码
'0x1'
>>> hex(-1 & 0xffffffff)  # 0xffffffff 得到负数的真实补码
'0xffffffff'
>>> -1 & 0xffffffff  # 4294967295 （ Python 将其认为正数）
4294967295

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

参考链接 作者：Krahets 链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def add(self, a: int, b: int) -> int:
        x = 0xffffffff
        # 获取负数的补码， 需要将数字与十六进制数 0xffffffff 相与。可理解为舍去此数字32位以上的数字，从无限长度变为一个32位整数。
        a, b = a & x, b & x
        _sum, _carry = 0, 0
        while True:
            _sum = a ^ b
            _carry = (a & b) << 1 & x  # 进位也要取负数的补码
            a = _sum
            b = _carry
            if _carry == 0:
                break
        # 返回前数字还原，已知0x7fffffff是最大正数的补码，若 a>0x7fffffff ，则说明a为负数。需执行~(a ^ 0xffffffff)操作，将补码还原至 Python 的存储格式。~(a ^ 0xffffffff)是将32位以上的位取反，即由0变为1，1至32位不变。
        return a if a <= 0x7fffffff else ~(a^x)

Extension

不使用新的变量，交换两个变量的值。比如有两个变量a、b，我们希望交换它们的值。有两种不同的方法：

基于加减法 基于异或运算
a = a + b a = a ^ b
b = a - b b = a ^ b
a = a - b a = a ^ b