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

题目描述

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

解题思路

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

代码

Python(2.7.3)

1
2
3
4
5
6
7
8
9
10
11
# -*- 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