C++笔记（6）：异或的妙用

异或的妙用

注：参考自《王道程序员求职宝典》。

1. 异或

按位异或（^）的运算规则为当两位相同时，则为0，不同时则为1。
异或满足交换律：A^B^C^D^E^F^B=A^C^D^E^F。

2.妙用方法

2.1 寻找数成对出现时缺失的某一个数

1. 如有一组数A、B、C、D、A、C、B，则A^B^C^D^A^C^B=D。

2. 给你一个由n-1个整数组成的未排序的序列，其元素都是1到n中的不同的整数，请写出一个寻找序列中缺失整数的线性时间算法：
   解法一：先求n-1个数之和Sum，然后计算n(n+1)/2 -sum可得，此种解法当n很大时，加法运算有可能溢出。
   解法二：先求从1到n共n个数的异或结果A，然后将该序列按照次序一次与A求异或，最后得到的数就是丢失的整数。

2.2 不使用第三方变量，交换两个变量的值

a=a^b;
b=a^b;
a=a^b;

即可以实现两变量交换。

2.3 不用算术运算符实现两个数的加法

对于二进制加法运算，若不考虑进位，则1+1=0，1+0=1，0+1=1，0+0=0，通过对比异或，不难发现，此方法与异或类似。因而排除进位，加法可以用异或来实现。
然后考虑进位，0+0的进位为0，1+0的进位为0，只有1+1时进位才为1，该操作与位运算的&操作相似。
那么加法运算可以这样实现：
1）先不考虑进位，按位计算各位累加（用异或实现），得值a；
2）然后计算进位，并将进位的值左移，得值b，若b为0，则a就是加法运算的结果，若b不为0，则a+b即得结果（递归调用该函数）；

int add_no_arithm(int a, int b)
{
	if(b == 0) return a;//没有进位时
	int sum = a^b;
	int carry = (a & b) << 1;
	return add_no_arithm(sum, carry);
}

2.4 位操作求两个数的平均值

(x&y)+((x^y) >> 1)。
如数x：01010，y：01100。x&y为01000，即取x、y中对应位都为1的位，并将结果的对应位置为1，相当于取得了都为1的位相加的一半。
x^y结果为00110，即取x、y中对应位只有一个为1的位，并将结果的对应位置1，由于最终结果是平均值，故除以2（用右移一位实现）。
以上两部分结果相加可得两数的平均值。