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

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

阅读量：4141 次

发布时间：2019-05-25

本文共 1818 字，大约阅读时间需要 6 分钟。

一、交换2个变量

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

例如，

[cpp]
 temp = a;  
 a = b;  
 b= temp;  

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

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

法1：

[cpp]
 #include <stdio.h>  
 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：

[cpp]
 #include <stdio.h>  
 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，异或运算满足交换律。因此将一组数依次异或，若里面只有一个只出现一次的数，其他的数都出现两次，则最后的结果必然是那个只出现一次的数。要找到两个数字就可以先通过异或整个数组，将得到的结果分组。然后依次安组异或就可以得到所求的值~

代码如下：

                         
#include<iostream>
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<length;i++){ 
        
ansXor^=date[i];              
//异或
    
}
    
int
pos=findFirstOne(ansXor);
    
num1=num2=0;
    
for
(
int
i=0;i<length;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<<ans1<<
" "
<<ans2<<endl;
    
else
        
cout<<
"error"
<<endl;
    
return
0;
}
        
      

你可能感兴趣的文章