AcWing 85.不用加减乘除做加法（奇葩Python版）

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷ 四则运算符号。

解题思路

设两数的二进制形式为a, b，则两数之和S = 非进位和 + 进位，同时非进位和与异或运算规律相同，进位与与运算规律相同（需左移一位）。 设n = a异或b, c = a&b<<1,循环求n和c，直至进位c = 0，此时和S = n，返回n即可。 知道上述规律之后，代码写起来似乎很简单，但如果你用Python写的话，就会遇到一个很奇葩的问题：在C、C++、Java中负数都是以补码形式存储的，因为在计算机系统中数值一律用补码来存储（CPU只有加法器），用补码的话加减法可以统一处理。奇葩就奇葩在在Python中没有int，long等不同长度变量，即没有变量位数的概念。所以下面Python代码可能引起不适，但在代码中都有注释。

代码实现

def add(a, b): """ :type a: int :type b: int :rtype: int """ # (n & 0xffffffff)进行这种变换的原因是,如果存在负数则需要转换成补码的形式,正数补码是他本身 # 同时限制了位数，舍去此数字 32 位以上的数字，从无限长度变为一个32位整数 a &= 0xffffffff b &= 0xffffffff # 无进位和与异或运算规律相同，进位和与运算规律相同（需左移一位） # 循环求无进位和和进位 ，直至进位= 0 while b != 0: carry = ((a & b) << 1) & 0xffffffff # 如果是负数,转换成补码形式 a ^= b b = carry # 如果是正数的话直接返回 # 应该是0x80000000是32位有符号整型的最小值, # 直接输入大于0x80000000的数时，计算机将其处理为原码而非补码。 if a < 0x80000000: return a else: # 1，对于32位的数字来说最高位是1则说明此数为负数。 # 2，python中数字没有位数的限制，若在python中表示负数， # 那么 在32位之前的所有位上，也和这32位中的最高位一样，是1。 # 3，~(n^0xffffffff) 操作，目的是将32位之前所有位都置1， # 并且保证低32位保持不变，以恢复负数在python中的表示方式。(负号+负数绝对值原码) # 此时n中高于32位的那些位上都是0，因为之前的操作都是限制在32位之内的。 # 因为n是负数，所以需要将这些位都置1。 return ~(a ^ 0xffffffff) # 是负数的话,转化成其原码,将补码还原至 Python 的存储格式