程序员面试金典面试题17。01。不用加号的加法

　　题目难度：中等
　　原题链接〔1〕
　　今天继续更新程序员面试金典系列，大家在公众号算法精选里回复面试金典就能看到该系列当前连载的所有文章了，记得关注哦题目描述设计一个函数把两个数字相加。不得使用或者其他算术运算符。示例：输入：a1，b1输出：2提示：a，b均可能是负数或0结果不会溢出32位整数题目思考不能用四则运算，那还能用哪些运算符来实现呢？解决方案思路我们先来尝试分析数字的二进制表示，看看能否用位运算来替代加法如果某一位的两个数字都是1，那么这一位的加法就会产生进位，所以与可以用来计算进位，而且显然进位是要左移一位的接下来考虑如何得到当前位的加法结果。异或在两个数字都为1或者都为0的情况下结果是0，否则结果是1，换言之异或就是不带进位的加法将上面两步结合在一起，我们就能把ab转换成（（ab）1）（ab），虽然这里仍然有加号，但是我们将其置为新的a和b，循环这个过程，直到进位变成0，这样最终异或结果就是两者之和了注意最终进位一定能变成0，这是因为如果有进位的话，进位是会不断左移的，而题目保证最终结果不会溢出，那么经过若干次循环后，一定会达到一个不需要进位的状态，不然无限左移就会溢出了CJAVA等语言分析到这里就OK了，但python需要特别处理负数问题。因为python的负数表示方法不是像其他语言那样的32位补码，而是更高位也全是1，这样在处理负数的时候必须手动模拟32位补码，才能正确得出结果，不然最后结果就不满足python正确的负数表示方式，而变成无符号正数了所以我们需要先将负数转成32位补码（0xFFFFFFFF，正数仍为自身，负数相当于32位补码形式，因为去掉了更高位上的1），然后利用上述结果求完之后，如果结果是负数（0x7FFFFFFF）的话再转成正常的python负数表示方式（（a0xFFFFFFFF），即先对低32位的取反，更高位不变，然后整体再取反，从而将大于等于32位的数字重新转成1）下面代码额外列出了Java版本，方便大家对比。Java的负数就是32位补码表示，所以不需要额外进行处理复杂度时间复杂度O（logN）：最多需要遍历所有位数，数字N的位数为logN空间复杂度O（1）：只需要维护常数个变量代码python3classSolution：defadd（self，a：int，b：int）int：32位数掩码mask0XFFFFFFFF32位数的最大正数posMx0X7FFFFFFFwhileb！0：a是不带进位的和，都要转成32位整数b是进位，都要转成32位整数循环直到进位为0，那么a就是最终结果sumWithoutCarry（ab）maskcarry（（ab）1）maska，bsumWithoutCarry，carry最终如果是32位负数的话，需要将其转回python正常的负数表示形式（高于32位的全是1，而不是32位负数那样更高位全为0），做法是先对低32位的取反，更高位不变，然后整体再取反，从而将大于等于32位的数字重新转成1returnaifaposMxelse（amask）JavaclassSolution｛publicintadd（inta，intb）｛while（b！0）｛intsumWithoutCarryab；intcarry（ab）1；asumWithoutCarry；bcarry；｝returna；｝｝参考资料
　　〔1〕
　　原题链接：https：leetcodecn。comproblemsaddwithoutpluslcci