剑指 Offer-不用加减乘除做加法（Python 实现过程遇到

2019-05-04 本文已影响0人 Oriharas

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

基本解题思路

回顾十进制加法原理

以 5 + 7 = 12 为例，分步走：

相加各位的值，不算进位，得到2。
计算进位值，得到10。如果这一步的进位值为0，那么第一步得到的值就是最终结果。
重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。

相同思想运用于二进制加法运算

同样我们可以用三步走的方式计算二进制值相加， $5=(101)_{二进制}，7=(111)_{二进制}$ ：

相加各位的值，不算进位，得到 010，二进制每位相加就相当于各位做异或操作，101 ^ 111。
计算进位值，得到 1010，相当于各位做与操作得到 101，再向左移一位得到 1010，(101 & 111) << 1。
重复上述两步，各位相加 010 ^ 1010 = 1000，进位值为 100 = (010 & 1010) << 1 。
继续重复上述两步：1000 ^ 100 = 1100，进位值为 0，跳出循环，1100 为最终结果。

代码实现

这里暂且沿着上述的思路，方便起见，用另一门动态语言 JavaScript 来实现题目的要求：

function add(num1, num2) {
    // write code here
    while (num2 !== 0) {
        let sum = num1 ^ num2
        let carray = (num1 & num2) << 1
        num1 = sum
        num2 = carray
    }
    return num1
}

从最终运行结果可以看出，上述代码是可以通过 OJ 的测试的：

image.png

Python 遇到的问题

用 Python 初步实现代码

将运行环境切换到 Python，根据 JS 的代码如法炮制：

class Solution:
    def Add(self, num1, num2):
        while num2:
            result = (num1 ^ num2)
            carry = ((num1 & num2) << 1)
            num1 = result
            num2 = carry
        return result

在 VSCode 中自行运行此段代码出现了无限循环无法退出得到返回结果的情况，提交到 OJ 上自然出现报错，提示如下：

不通过

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为0.00%

问题的初步分析

经过进一步的调试分析，再经过对 Python 的相关资料查阅，得出了此问题的根源在于 Python 中整型变量的一些特性：

在 Python 2 时代，整型有 int 类型和 long 长整型，int 长度为机器位长，通常都是 32 位，超过这个范围的整数就自动当长整数处理，而长整数的范围几乎完全没限制。

在 Python 3 后，统一使用了 long 长整型。这也是吸引科研人员的一部分了，适合大数据运算，不会溢出，也不会有其他语言那样还分短整型、整型和长整型等等。因此 Python 就降低其他行业的学习门槛了。

所以最关键的问题就出在，Python 中的整型变量不会溢出之上。至于要理解这一点，需要复习一下 计算机组成原理 的一些基础知识。

计算机的一些基础知识

机器数和真值

机器数

一个数在计算机中的二进制表示形式，叫做这个数的机器数。机器数是带符号的，在计算机用一个数的最高位存放符号，正数为 0，负数为 1。

比如，十进制中的数 +3 ，假设计算机字长为 8 位，转换成二进制就是 00000011。同理 $-3 = (10000011)_{二进制}$ 。

那么，这里的 00000011 和 10000011 就是机器数。

真值

因为第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000011，其最高位1代表负，其真正数值是 -3 而不是形式值131（10000011转换成十进制等于131）。所以为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值，例如：

$[0000 0001]_{真值} = +000 0001=+1$
$[1000 0001]_{真值}= –000 0001=–1$

原码、反码和补码的基础概念和计算方法

原码

原码就是符号位加上真值的绝对值，即用第一位表示符号，其余位表示值。比如如果是8位二进制：

$[+1]_{原码} = 0000 0001$
$[-1]_{原码} = 1000 0001$

第一位是符号位。因为第一位是符号位，所以 8 位二进制数的取值范围就是：[1111 1111, 0111 1111]，即 [-127 , 127]。原码是人脑最容易理解和计算的表示方式。

反码

反码的表示方法是：正数的反码是其本身；负数的反码是在其原码的基础上，符号位不变，其余各个位取反：

$[+1] = (00000001)_{原码} = (00000001)_{反码}$
$[-1] = (10000001)_{原码} = (11111110)_{反码}$

可见如果一个反码表示的是负数，人脑无法直观的看出来它的数值。通常要将其转换成原码再计算。

补码

补码的表示方法是：正数的补码就是其本身；负数的补码是在其原码的基础上，符号位不变，其余各位取反, 最后 +1（即在反码的基础上 +1）：

$[+1] = (00000001)_{原码} = (00000001)_{反码} = (00000001)_{补码}$
$[-1] = (10000001)_{原码} = (11111110)_{反码} = (11111111)_{补码}$

对于负数，补码表示方式也是人脑无法直观看出其数值的。通常也需要转换成原码在计算其数值。

计算方法

人脑可以知道第一位是符号位，在计算的时候我们会根据符号位，选择对真值区域的加减。但是对于计算机，加减乘数已经是最基础的运算，要设计的尽量简单。计算机辨别 符号位 显然会让计算机的基础电路设计变得十分复杂。于是人们想出了将符号位也参与运算的方法。根据运算法则减去一个正数等于加上一个负数，即：1 - 1 = 1 + (-1) = 0，所以机器可以只有加法而没有减法，这样计算机运算的设计就更简单了。

原码计算十进制的表达式：

$1 - 1 = 1 + (-1) = (00000001)_{原码} + (10000001)_{原码} = (10000010)_{原码} = -2$

如果用原码表示，让符号位也参与计算，显然对于减法来说，结果是不正确的。这也就是为何计算机内部不使用原码表示一个数，为了解决原码做减法的问题, 出现了反码：

$1 - 1 = 1 + (-1) = (00000001)_{原码} + (10000001)_{原码} = (10000010)_{原码}$

$= (0000 0001)_{反码} + (1111 1110)_{反码} = (1111 1111)_{反码} = (1000 0000)_{原码} = -0$

发现用反码计算减法，结果的真值部分是正确的。而唯一的问题其实就出现在 0 这个特殊的数值上。虽然人们理解上 +0 和 -0 是一样的，但是 0 带符号是没有任何意义的。而且会有 $(0000 0000)_{原码}$ 和 $(1000 0000)_{原码}$ 两个编码表示0。

于是补码的出现，解决了 0 的符号以及两个编码的问题：

$1 - 1 = 1 + (-1) = (00000001)_{原码} +(10000001)_{原码}$

$= (0000 0001)_{补码} + (1111 1111)_{补码} = (0000 0000)_{补码}= (0000 0000)_{原码}$

这样 0 用 $(0000 0000)_{补码}$ 表示，而以前出现问题的 -0 则不存在了。而且可以用 $(1000 0000)_{补码}$ 表示 -128：

$(-1) + (-127) = (1000 0001)_{原码} + (1111 1111)_{原码} = (1111 1111)_{补码} + (1000 0001)_{补码} = (1000 0000)_{补码}$

-1 - 127 的结果应该是 -128，在用补码运算的结果中， $(1000 0000)_{补码}$ 就是 -128。但是注意因为实际上是使用以前的 -0 的补码来表示 -128，所以 -128 并没有原码和反码表示。(对 -128 的补码表示 $(1000 0000)_{补码}$ 算出来的原码是 $(0000 0000)_{原码}$ ，这是不正确的。)

使用补码，不仅仅修复了 0 的符号以及存在两个编码的问题，而且还能够多表示一个最低数。这就是为什么8位二进制，使用原码或反码表示的范围为 [-127, +127]，而使用补码表示的范围为 [-128, 127]。

寻找 Python 造成的问题

因为机器使用补码，所以对于编程中常用到的32位int类型，可以表示范围是： $[-2^{31}, 2^{31}-1]$ ，因为第一位表示的是符号位。而使用补码表示时又可以多保存一个最小值。

而本题的 OJ 所使用的测试用例取值范围也正是介于 $[-2^{31}, 2^{31}-1]$ ，为了更简单清晰地对比解释 Python 出现问题的原因和背后的原理，经过一系列实验，我选择了 (1, -1) 来作为例子。同时为了明了地展现运行的过程，这里在正常运行的 JS 代码当中的循环结构体里加入一句打印语句，来观测每次 num2 对应的结果：

function add(num1, num2) {
    while (num2 != 0) {
        let sum = num1 ^ num2
        let carray = (num1 & num2) << 1
        num1 = sum
        num2 = carray
        console.log(num2) //插入的打印语句
    }
    return num1
}

console.log("1 + (-1) = " + add(1, -1))
console.log("-(2^31) = " + -(2 ** 31))

打印结果如下所示：

2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
-2147483648
0
1 + (-1) = 0
-(2^31) = -2147483648

从结果可以很清晰地看出，当循环执行到倒数第二步的时候，此刻 num2 的数值为 $-2147483648 = -2^{31} = (1000,0000,0000,0000,0000,0000,0000,0000,0000)_{补码}$ ，正好触碰到了 32 位 int 类型的边界。如果再执行一步算数左移动 <<，那么将溢出得到 0，从而终止循环。

现在需要类似地执行 Python 之前那一段不完全正确的代码来对比结果，由于那一段代码会陷入无限循环的状态，所以需要打断点调试手动来到上述的倒数第二步的位置，结果如下所示：

image.png

结果显而易见了，同样的地方，但是 Python 执行出来结果为 2147483648 = $2^{31}$ ，这超出了 int 类型的边界（ $[-2^{31}, 2^{31}-1]$ ）了。这就是 Python 和其他语言不太一样的地方，就是对负数的二进制表示。Python 里的数是无所谓 Overflow 的，即没有位数限制，因此也就无所谓补码，因为补码都是相对于位数来说的，32 位补码和 16 位补码，肯定是不一样的。但是这样就导致了一个问题，就是无法直接得到32位二进制补码。

Python 中正负数的判断及其还原

正数与边界数 0xffffffff 按位与（&）操作后仍得到这个数本身：

15 & 0xffffffff —> 15

负数与边界数按位与（&）操作后得到的是对应二进制数的真值：

-1 & 0xffffffff —> 4294967295

$4294967295 = 2^{32} - 1 = (1111,1111,1111,1111,1111,1111,1111,1111)_{二进制}$ 。而 1111,1111,1111,1111,1111,1111,1111,1111 正好是 -1 在 int 类型下的补码表示。

为了便于理解，以一个小边界为例：

-15 & 0xff —> 241

241 对应的二进制数为： 11110001，8 位状态下 -15 的补码。

通过查看符号位（最高位，即与 0x7ffffffff ）断a为正数还是负数，正数则直接返回。负数则返回-((num1 - 1) ^ 0xffffffff)。所以最终的正确代码为：

class Solution:
    def Add(self, num1, num2):
 
        while num2:
            result = (num1 ^ num2) & 0xffffffff
            carry = ((num1 & num2) << 1) & 0xffffffff
            num1 = result
            num2 = carry
        if num1 <= 0x7fffffff:
            result = num1
        else:
            result = -((num1 - 1) ^ 0xffffffff)
        return result

此题另外一种解法

可以用 ctypes 来在 Python 中定义 C 语言的数据类型：

import ctypes
class Solution:
    def Add(self, num1, num2):
        a = ctypes.c_int32(num1).value
        b = ctypes.c_int32(num2).value
        while b != 0:
            carry = ctypes.c_int32(a & b).value
            a = ctypes.c_int32(a ^ b).value
            b = ctypes.c_int32(carry << 1).value
 
        return a