异或运算 ^ 变量交换及找出现一次的数

一、交换2个变量

如果想要交换2个变量，一般的做法是引入第三个变量，

例如，

temp = a;
a = b;
b= temp;

这样2个变量中的值就实现了交换。那能不能不引入其他变量就可以实现变量值的交换呢？答案是肯定的。

用异或操作可以实现，有2种实现方法，本质上是一样的。

法1：

#include
int main()
{
    int a,b;
    while(1)
    {
        scanf("%d %d",&a,&b);
        a = a^b;          //(1)
        b = a^b;          //(2)
        a = a^b;          //(3)
        printf("%d %d\n",a,b);
    }
    return 0;
}

法2：

#include
int main()
{
    int a,b;
    while(1)
    {
        scanf("%d %d",&a,&b);
        b = a^b;        //(1)
        a = a^b;        //(2)
        b = a^b;        //(3)
        printf("%d %d\n",a,b);
    }
    return 0;
}

因为2种方法本质一样，就方法一进行一下证明。

异或操作满足结合律和交换律，且由异或操作的性质知道，对于任意一个整数a^a=0；

证：(第(2)步中的a) a = a^b = (将第(1)步中的b代入b) a^(a^b) = b;

(第(3)步中的b)b = a^b = (将第(1)步中的b代入b，将第(2)步中的a代入a) a^b^a^a^b = a^a^a^b^b = a;

证毕

http://blog.csdn.net/love_cppandc/article/details/7023238

二、求出现一次的数

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字

这道题利用异或的几个性质：任何数与其本身异或值都为0，异或运算满足交换律。因此将一组数依次异或，若里面只有一个只出现一次的数，其他的数都出现两次，则最后的结果必然是那个只出现一次的数。要找到两个数字就可以先通过异或整个数组，将得到的结果分组。然后依次安组异或就可以得到所求的值~

代码如下：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include using namespace std; int findFirstOne(int value); bool testBit(int value,int pos); int findNums(int date[],int length,int &num1,int &num2){     if(length<2){return -1;}     int ansXor=0;     for(int i=0;i         ansXor^=date[i];              //异或     }     int pos=findFirstOne(ansXor);     num1=num2=0;     for(int i=0;i         if(testBit(date[i],pos))             num1^=date[i];         else             num2^=date[i];     }     return 0; } int findFirstOne(int value){    //取二进制中首个为1的位置     int pos=1;     while((value&1)!=1){         value=value>>1;         pos++;     }     return pos; } bool testBit(int value,int pos){ //测试某位置是否为1     return ((value>>pos)&1); } int main(void){     int date[10]={1,2,3,4,5,6,4,3,2,1};     int ans1,ans2;     if(findNums(date,10,ans1,ans2)==0)         cout<     else         cout<<"error"<     return 0; }