[剑指Offer]不用加减乘除做加法

题目描述

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

解题思路

• 将两个数直接按位相加不进位，二进制中即为异或运算；
• 求出两个数需要进位的位置，二进制中即为按位与操作，之后左移一位；
• 将前面两部分结果作为初始的两个整数进行循环，直到不需要进位为止。
• 坑：Python中没有位数这个概念，需要判断结果的正负(这部分没怎么看懂，见参考链接)。

代码

Python(2.7.3)

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        while num2 != 0:
            sum1 = (num1 ^ num2) & 0xffffffff
            num2 = ((num1 & num2) << 1) & 0xffffffff
            num1 = sum1
        if num1 <= 0x7fffffff:
            return num1
        return ~(num1 ^ 0xffffffff)

运行时间：37ms
占用内存：5852k

参考

https://www.nowcoder.com/questionTerminal/59ac416b4b944300b617d4f7f111b215?toCommentId=1177972