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

题目描述

https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

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

提示：

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

解题思路

这个题考的是加法器的实现原理，即循环对每一位求非进位（异或）和进位（位与然后左移1位）。
我们可以用三步法来解决本题：
1. 先用十进制来举个例子。假如我们要算 8 + 13，那么第一步我们只做每一位的相加但是不进位，那么此时相加的结果为 11（个位 8 + 3 相加不进位是 1，十位 0 + 1 相加是 1）；第二步只算进位，只有 8 + 3 中有进位，所以进位的值是 10；第三步把前面两步的结果加起来，则有：11 + 10 = 21。刚好等于 8 + 13 = 21。
2. 那如果我们把这三步法移植到二进制上来（因为位运算是在二进制形式的数上进行的），8 的二进制是 1000，13 的二进制是 1101。那么经过第一步我们会得到：0101；第二步会得到：10000；第三步将前两步的数相加，得到：10101。刚好等于 1000 + 1101 = 10101。
3. 明白了三步法，我们现在把二进制与位运算联系起来。我们可以观察到，第一步不算进位的加法操作，与 异或运算 的结果是一样的，在我们的例子中就是： 1000 ^ 1101 = 0101；第二步只算进位的操作，跟 位与运算再往左移一位 的结果是一样的，在我们的例子中就是：(1000 & 1101) << 1 = 10000；第三步则是将前两步相加，聪明的你肯定能想到，第三步可以 复用 第一步！因为都是加法操作！也就是说第三步可以通过 第一步的结果 ^ 第二步的结果 来实现。
Python 负数的存储：
Python，Java 等语言中的数字都是以 补码 形式存储的。但 Python 没有 int , long 等不同长度变量，即在编程时无变量位数的概念。
获取负数的补码： 需要将数字与十六进制数 0xffffffff 相与。可理解为舍去此数字 32 位以上的数字（将 32 位以上都变为 0），从无限长度变为一个 32 位整数。
返回前数字还原： 若补码a 为负数（ 0x7fffffff 是最大的正数的补码 ），需执行 ~(a ^ x) 操作，将补码还原至 Python 的存储格式。 a ^ x 运算将 1 至 32 位按位取反； ~ 运算是将整个数字取反；因此， ~(a ^ x) 是将 32 位以上的位取反，1 至 32 位不变。

解题代码

class Solution:
    def add(self, a, b):
        x = 0xffffffff
        a, b = a & x, b & x
        while b:
            carry = (a & b) << 1 & x
            total = a ^ b
            a = total
            b = carry
        return a if a <= 0x7fffffff else ~(a ^ x)

执行结果

执行结果：通过
执行用时：40 ms, 在所有 Python3 提交中击败了58.12%的用户
内存消耗：14.8 MB, 在所有 Python3 提交中击败了74.30%的用户