6.14如何不使用^操作实现异或运算

6.14如何不使用^操作实现异或运算

【出自YMX面试题】

难度系数：★★★☆☆ 被考察系数：★★★★☆

题目描述：

不使用^操作实现异或运算。

分析与解答：

最简单的方法是遍历两个整数的所有的位，如果两个数的某一位相等，那么结果中这一位的值为0，否则结果中这一位的值为1，实现代码如下：

程序的运行结果如下：

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。实现代码如下：

funxor（x：Int，y：Int）：Int{

returnxoryand（x.inv（）ory.inv（））

}

算法性能分析：

这种方法的时间复杂度为O（N）。