371. Sum of Two Integers - Python

Posted on   |   Updated on | In | | Visitors

不用加减乘除做加法

剑指Offer中也出现过此题，此篇文章着重分析一下为什么Python需要做一些多余的操作。

根据书中的分析，大致分为三步：

  • 相加但不进位，使用^
  • 进位使用&和<<
  • 前两步结果相加

这里不再赘述详细过程。那么我们不难写出代码：

1
2
3
4
5
6
7
def get_sum(a, b):
    res, carry = 0, 0
    while b != 0:
        res = a ^ b
        carry = (a & b) << 1
        a, b = res, carry
    return res

但是当输入a=-1, b=1时，会发现程序超时。
先来看看正常的32位int类型运算时发生了什么，因为进行位运算时要使用补码进行运算，而正数的反码和补码都是本身，负数的反码为除符号位，其它按位取反，负数的补码为反码+1。下面列出了32为整数传入a=-1,b=1时，每次循环中a和b的补码。

a的原码 a的补码 b的补码 a ^ b a & b
10…0001 11…1111 00…0001 11…1110 00…0001
10…0010 11…1110 00…0010 11…1100 00…0010
10…0100 11…1100 00…0100 11…1000 00…0100
⋮ ⋮ ⋮ ⋮ ⋮
110…000 110…000 010…000 100…000 010…000
100…000 100…000 100…000 000…000 100…000
000…000 000…000 000…000 ‘break’ ‘break’

可以看出由于位数的限制，b和a最后都变成了0。因为Python中的int没有范围限制，所以这就是为什么会死循环的原因。

如何解决这个问题呢？我们需要在b的补码变成1000…000(32个0)时终止循环，如何将一个一个无限位的整型转成32位呢，想到了&，所以我们找到一个mask=2**32-1也就是32个1，用一个无限位的值和mask进行与运算，就变成了上述表格中的例子，于是我们将代码改为：

1
2
3
4
5
6
7
8
def getSum(self, a, b):
    res, carry = 0, 0
    mask = 0xFFFFFFFF
    while b != 0:
        res = (a ^ b) & mask
        carry = ((a & b) << 1) & mask
        a, b = res, carry
    return res

提交之后还是不能通过测试用例，当a=-12, b=-8时输出了4294967276而不是-20。好，把mask先去掉，传入这两个值，发现可以正常输出-20，那么这里的mask是怎么造成了一些副作用的。
再来分析一下这两个参数下，具体的过程是怎样的。

为了方便DEBUG，我们添加一些输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def get_sum(self, a, b):
    mask = 0xFFFFFFFF
    res, carry = 0, 0
    while b != 0:
        print('bin({}) = {}, bin({}) = {}'.format(a, bin(a), b, bin(b)))
        res = (a ^ b) & mask
        # res = (a ^ b) 
        print('\t res = {}, bin(res) = {}'.format(res, bin(res)))
        carry = ((a & b) << 1) & mask
        # carry = ((a & b) << 1)
        print('\t \t a&b = {}, (a&b)<<1 = {}, carry = {}'.format((a&b), ((a&b)+1), carry))
        a, b = res, carry
    # return res if res <= MAX else ~(res ^ mask)
    return res

输出如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Finished in 20 ms
bin(-12) = -0b1100, bin(-8) = -0b1000
	 res = 12, bin(res) = 0b1100
	 	 a&b = -16, (a&b)<<1 = -15, carry = -32
bin(12) = 0b1100, bin(-32) = -0b100000
	 res = -20, bin(res) = -0b10100
	 	 a&b = 0, (a&b)<<1 = 1, carry = 0
-20
Finished in 24 ms
bin(-12) = -0b1100, bin(-8) = -0b1000
	 res = 12, bin(res) = 0b1100
	 	 a&b = -16, (a&b)<<1 = -15, carry = 4294967264
bin(12) = 0b1100, bin(4294967264) = 0b11111111111111111111111111100000
	 res = 4294967276, bin(res) = 0b11111111111111111111111111101100
	 	 a&b = 0, (a&b)<<1 = 1, carry = 0
4294967276

可以看到在进行-15&mask时，carry变成了一个很大的正数，并丢失了符号。此处为个人猜想，当负数与mask进行与运算时，比如-2，此时-2的补码变为11…10，一个33-bit的数字，然后和32位的mask与操作后，变为了一个33位的正数。

有一个公式可以帮我们还原a，如果一个负数n，它的无符号的32位补码是m，那么m=~(n ^ mask) 或者n=~(m ^ mask)

于是代码修改为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def getSum(self, a, b):
    MASK = 0xffffffff

    # in Python, every integer is associated with its two's complement and its sign.
    # However, doing bit operation "& mask" loses the track of sign. 
    # Therefore, after the while loop, a is the two's complement of the final result as a 32-bit unsigned integer. 
    while b != 0:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK

    # a is negative if the first bit is 1
    if (a >> 31) & 1:
        return ~(a ^ MASK)
    else:
        return a

虽然python进行大数字运算很方便，但是无限制位数往往会对位运算的操作中产生一些陷阱。如果可以直接转成Java中那种32的int，岂不是没有这么多麻烦了，好在numpy为我们提供了这样的方法。

1
2
3
4
5
6
7
import numpy as np

class Solution(object):
    def getSum(self, a, b):
        while b != 0:
            a, b = np.int32(a ^ b), np.int32((a & b) << 1)
        return int(a)

最后要再转回int，否则是没法通过测试用例的。

参考：