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

Solutions

  四则运算都不让用,那就用位运算了。三步走策略:

  • ①只做各位相加不进位(可以用异或来处理,和异或结果相同)
  • ②进位:可以想象为两个数先做位与运算,然后左移一位
  • ③把前两个步骤的结果相加,重复前两步,直到不产生进位为止。在Python中做位运算,需要做越界检查。
# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        while num2:
            sum_ = (num1 ^ num2) & 0xffffffff
            carry = ((num1 & num2)<<1)& 0xffffffff
            num1 = sum_
            num2 = carry
        if num1<0x7fffffff:
            return num1
        else:
            return ~(num1^0xffffffff)
# 运行时间:31ms
# 占用内存:5728k

拓展:不使用新的变量,交换两个变量的值。

①基于加减法      ②基于异或

$a=a+b$        $a=a^b$

$b=a-b$        $b=a^b$

$a=a-b$        $a=a^b$

References

  1. 047. 不用加减乘除做加法