塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-65不用加减乘除做加法-python

《剑指offer》python实现系列,全目录

题目描述

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

剑指offer方法:

利用位运算,转为二进制做加法

首先我们分析是如何做十进制加法的,比如是如何得出5+17=22这个结果的。实际上,我们可以分成三步进行:第一步只做各位相加不进位,此时相加的结果是12(个位数5和7相加不要进位是2,十位数0和1相加结果是1):第二步做进位,5+7中有进位,进位的值是10第三步把前面两个结果加起来,12+10的结果是22,刚好5+17=22。

求两数之和四则运算都不能用,那还能用什么?对数字做运算,除四则运算之外,也就只剩下位运算了。位运算是针对二进制的,我们就以二进制再来分析一下前面的“三步走”策略对二进制是不是也适用。

5的二进制是101,17的二进制是10001.我们还是试着把计算分成三步:第一步各位相加但不计进位,得到的结果是10100(最后一位两个数都是1,相加的结果是二进制的10.这一步不计进位,因此结果仍然是0)
第二步记下进位,在这个例子中只在最后一位相加时产生一个进位,结果是二进制的10:第三步把前两步的结果相加,得到的结果是10110,转换成十进制正好是22.由此可见“三步走”策略对二进制也是适用的。

(二进制相加不算加法吗?)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
C++ 思路
class Solution:
def Add(self, num1, num2):
# write code here
while num2: #while是为了防止多次进位
#第一步
sum = num1 ^ num2 #异或相同为0,相异为1
#第二步
carry = (num1 & num2) <<1 #将进位向左移
#第三步
num1 = sum
num2 = carry

return num1

注意python没有无符号右移操作,所以需要越界检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
class Solution:
def Add(self, num1, num2):
# write code here
while num2: #while是为了防止多次进位
#第一步
sum = (num1 ^ num2) & 0xffffffff#异或相同为0,相异为1
#第二步
carry = ((num1 & num2) <<1)& 0xffffffff #将进位向左移
#第三步
num1 = sum
num2 = carry

if num1 <= 0x7fffffff:
result = num1
else:
result = ~(num1^0xffffffff)

return result

拓展

不用新变量,交换两个变量的值

①基于加减法 ②基于异或

a=a+b a=a^b

b=a-b b=a^b

a=a-b a=a^b

if help:小手一抖点个广告 or 大手一挥资助一下