python3 下的位运算模拟加法

题目：用位运算模拟加法

主要考虑到有(a + b) == (a^b) + (a & b) << 1 的关系，一直重复下去直到(a & b) << 1等于0即可

用C++语言的话，代码如下

#include <iostream>
using std::cout;
using std::endl;
int add(int a, int b) {
    return b ? add(a ^ b, (a & b) << 1) : a;
}

int sub(int a, int b) {
    return add(a, add(~b, 1));
}
int main() {
    cout << sub(79, 78) << endl;
    return 0;
 }

该代码在C++下能正确运行。

但在python下

def add(a,b):
    print("a:{} b:{}".format(a,b))
    return a if b == 0 else add(a ^ b, (a&b)<<1)

def sub(a,b):
    return add(a,add(~b,1))

print(sub(79,78))

会报错

RecursionError: maximum recursion depth exceeded while calling a Python object

主要原因可以看print最后打印的ab值

a:-334846439745708537796382827831250565800439003657979252326171996365734703476542538279124493379904955664873335286735358382870982901778848138624518049209330462622955242963257218294408581408199098183686068192282702343236935664606211486223923248314908216080349889927704442739388432239144512088662677127167 b:334846439745708537796382827831250565800439003657979252326171996365734703476542538279124493379904955664873335286735358382870982901778848138624518049209330462622955242963257218294408581408199098183686068192282702343236935664606211486223923248314908216080349889927704442739388432239144512088662677127168

a:-669692879491417075592765655662501131600878007315958504652343992731469406953085076558248986759809911329746670573470716765741965803557696277249036098418660925245910485926514436588817162816398196367372136384565404686473871329212422972447846496629816432160699779855408885478776864478289024177325354254335 b:669692879491417075592765655662501131600878007315958504652343992731469406953085076558248986759809911329746670573470716765741965803557696277249036098418660925245910485926514436588817162816398196367372136384565404686473871329212422972447846496629816432160699779855408885478776864478289024177325354254336

这个主要原因是因为python里面int并非是按32位进行存储，会自动进行扩充，以容纳大数运算，因此用位运算来模拟加法会因为无法利用溢出截断导致无法成功。

因此上述代码需要如下修改

def add(a,b):
    print("a:{} b:{}".format(a,b))
    return a & 0xFFFFFFFF if b == 0 else add((a ^ b) & 0xFFFFFFFF, ((a&b)<<1)  & 0xFFFFFFFF)

def sub(a,b):
    return add(a,add(~b,1))

print(sub(79,78))

作者