异或运算的使用

异或运算可以方便记成无进位相加。

异或运算的性质：

（1）0^N=N,N^N=0；

（2）异或运算满足交换律和结合律。

异或的运用：

（1）交换两个数

//设有变量a，b，交换a，b两数
a=a^b;
b=a^b;
a=a^b;

异或常见题目：

（1）一个数组中有一个数出现了奇数次，其它数都出现了偶数次，怎么找到并打印出这个数？

//设有满足题意的int型数组arr
int eor=0;
for(i=0;i<arr.length;i++)
{
	eor^=arr[i];
}

（2）怎么把一个int类型的数，提取其最右侧的1出来？

//设有一个int型的数N
//N取反，通过加1就能找到原N右边的第一个1,再与上原N即可
int ANS=N&(~N+1);  

(3)一个数组中有两种数出现了奇数次，其它数都出现了偶数次，怎么找到并打印这两种数？

//设有满足题意的int型数组arr
int eor=0;
for(int i=0;i<arr.length;i++)
{
	eor^=arr[i]; //找到两个目标数a，b的与运算后的结果，存放于eor中
                 //eor必然不为0，即二进制下必有某位i为1
                 //也即目标数a，b中必有a的i为1，b的i为0或反之即反
}
//提取出最右边的1，就以该位为目标位了
int rightOne=eor&(~eor+1);
//eor'
int onlyOne=0;  //用onlyOne来保存目标位为1的那个目标数
//通过判断所有数的目标位是否为1，来将所有数分成两组，a与b必不再同一组
for(int i=0;i<arr.length;i++)
{
	if(arr[i]&rightOne!=0)  //或者arr[i]&rightOne==0
    {
    	onlyOne^=arr[i];
    }
}
cout<<onlyOne<<" "<<onlyOne^eor<<endl;

（4）求一个int型数N中1的个数

//设有int型数N
int count=0;
while(N)
{
	int rightOne=N&(~N+1);  //找到右1
    count++;
    N^=rightOne;  //N异或右1,即减去右1
}