JZ65 不用加减乘除做加法

发表于 分类于 本文字数： 420 阅读时长 ≈ 2 分钟

JZ65 不用加减乘除做加法

描述

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

数据范围：两个数都满足 $−10≤n≤1000$
进阶：空间复杂度 $O(1)$，时间复杂度 $O(1)$

示例1

1
2
输入：1,2
返回值：3

示例2

1
2
输入：0,0
返回值：0

题解

终于还是到位运算了，唤醒了我死去已久的记忆，首先还是回顾一下python里位运算的相关符号，按照优先级从高至低：

1
2
3
4
5
~			# 取反
<< , >>		 	# 移位
&			# 与
^			# 异或
|			# 或

其中，与 & 、或 | 、异或 ^ 都满足交换律和结合律。由此我们现在可以回到这道题，不使用加减乘除的情况下仅使用位运算来实现加法。

加法一般会产生两个结果，第一是和，第二是进位，在位运算中就需要逐个实现。

$a\textasciicircum b$可以表示$a+b$在没有进位的情况下的和，然后再求a&b，获得需要进位的位，再将其右移一位，把进位加上去。重复此流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
例：5+3							# 0101+0011
step1-------------------------------------------------------------------------
		0101					0101
异或		0011			与		0011
和		0110			进位		0001	-右移->	0010
step2-------------------------------------------------------------------------
		0110					0110
异或		0010			与		0010
和		0100			进位		0010	-右移->	0100
step3-------------------------------------------------------------------------
		0100					0100
异或		0100			与		0100
和		0000			进位		0100	-右移->	1000
step4-------------------------------------------------------------------------
		0000					0000
异或		1000			与		1000
和		1000			进位		0000	-为0->	结束
end---------------------------------------------------------------------------
结果为	1000 -十进制-> 8

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 
# @param num1 int整型 
# @param num2 int整型 
# @return int整型
#
class Solution:
    def Add(self , num1: int, num2: int) -> int:
        # write code here
        add = num2
        sum = num1

        while add:
            temp = sum ^ add
            add = (sum & add) << 1
            sum = temp & 0xFFFFFFFF
        return sum if sum >> 31 == 0 else sum - 4294967296