题目:写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
代码:
# -*- coding:utf-8 -*-
class Solution:
def Add(self, num1, num2):
# write code here
tsum=(num1^num2)&0xFFFFFFFF#step1:相加但不计进位的结果,因python无位数限制,在此将其限定在32位
carry=((num1&num2)<<1)&0xFFFFFFFF#step2:求出进位结果,并将其转成32位
while(carry):#step3:当有进位时,需要将step1和step2的结果继续相加,即重复step1和stwp2.
num1=tsum
num2=carry
tsum=(num1^num2)&0xFFFFFFFF#相加但不计进位的结果,并将其转成32位
carry=((num1&num2)<<1)&0xFFFFFFFF#求出进位结果,并将其转成32位
#直到carry为0,即:直到没有进位为止。
#最后返回最终的异或(相加)结果
#注意:8位可以表示的数值范围在 -128到+127,即(100000000-01111111),第一位是符号位。
#所以32位可以表示的数值范围在 1000 0000 0000 0000 0000 0000 0000 0000到0x7FFFFFFF,即-2147483648到2147483647,但
#是python没有位数限制,即不存在最高位溢出,不会将表示负数的最高位‘1’认为是符号位,所以会将1000 0000 0000 0000 0000 0000 0000 0000认为是2147483648。
#因此需要进行越界检查,将负数进行相应处理: ~(tsum^0xFFFFFFFF)
return tsum if tsum<=0x7FFFFFFF else~(tsum^0xFFFFFFFF)#python的位运算没有无符号右移操作,需要越界检查
python相关的位操作 (以下部分转自原文:https://blog.csdn.net/u013061183/article/details/78525807)
由于数值在计算机中的存储采用的是补码存储,所以一般的位运算都是基于补码进行的。现假设某计算机字长为8位 。
原码: 正数转化为2进制,负数第一位取1。
1 : 0000 0001
-1 : 1000 0001
反码:
正数的原码不变,负数为原码符号位不变,其余取反。
1 : 0000 0001
-1 : 1111 1110
补码:
正数原码不变,负数为原码符号位不变,其余的按位取反再加一,故1000 0000可以表示为-128
1: 0000 0001
-1 :1111 1111
在这个链接里面有原理的详尽的解释:
https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html
Python中的按位运算符有:左移运算符(<<),右移运算符(>>),按位与(&),按位或(|),按位翻转(~)。这些运算符中只有按位翻转运算符是单目运算符,其他的都是双目运算符。
python中的&:
A&B
利用A,B的补码按位与(1&1=1,1&0=0,0&0=0),然后把得到的补码还原,1&1=1
python中的|:
A|B
利用A,B的补码按位并(1|1=1,1|0=1,0|0=0),然后把得到的补码还原。1|0=1
python中的^:
A^B
利用A,B的补码按位异或(1^1=0,1^0=1,0^0=0,即相同为0,不同为1),然后把得到的补码还原。1^1=0
python中的~:
~A
A的补码按位取反(~1=0,~0=1),得到的为补码,输出还原结果。~1=-2(因为1的补码为0000 0001,按位取反为1111 1110 这个是-2的补码)
python中的>>:
A>>n
A的补码按位向右移动n位,左边缺少的地方补符号位(即正数补0,负数补1)(相当于除以2的n次方取整 -8>>1=-8//2=-4 -8>>2=-8//4=-2)
python中的<<:
B<< n
B的补码按位向做移动n位,右边缺少的补0(相当于乘以2 ,4<<1=4*2=8,4<<2=4*4=16)
注意:python的<<,与c和java中的不一样,因为他们有字符长度,8位,16位,32位,所以32位为例,如果1<<31=-2147483648,1<<32=0,因为高位溢出,但是在python中1<<31=2147483648,1<<32=4294967296,因为在python中整数是不限长度的(即不存在高位溢出)