【正确答案】最简单的方法是遍历两个整数的所有的位,如果两个数的某一位相等,那么结果中这一位的值为0,否则结果中这一位的值为1,实现代码如下:
class MyXOR:
def __init__(self):
self.BITS=32
#获取x与y的异或的结果
def xor(self,x,y):
res=0
i=self.BITS-1
while i>=0:
#获取x与y当前的bit值
b1=(x&(1<<i))>0
b2=(y&(1<<i))>0
#只有这两位都是1或0的时候结果为0
if (b1==b2):
xoredBit=0
else:
xoredBit=1
res<<=1
res|=xoredBit
i-=1
return res
if __name__=="__main__":
x=3
y=5
mx=MyXOR()
print mx.xor(x,y)
程序的运行结果为:
6
下面介绍另外一种更加简洁的实现方法:x^y=(x|y)&(~x|~y),其中x|y表示如果在x或y中的bit为1,那么结果的这一个bit的值也为1,显然这个结果包括三部分:这个bit只有在x中为1,只有在y中为1,在x和y中都为1,要在这个基础上计算出异或的结果,显然要去掉第三种情况,也就是说去掉在x和y中都为1的情况,而当一个bit在x和y中都为1的时候“~x|~y”的值为0,因此(x|y)&(~x|~y)的值等于x^y。实现代码如下:
def xor(x,y):
return (x|y) &(~x|~y)
算法性能分析:
这种方法的时间复杂度为O(N)。
【答案解析】[考点] 如何不使用^操作实现异或运算