异或操作的高效使用

异或操作的基本规则是对应位相同为0，相异为1。异或操作有很多妙用，这里只选取一类典型的题目，在此写出自己的看法，由于视野有限，见笑了！

a=x^a^x.

1.一个整形数组记录了1到n的所有整数，有且仅有一个缺省，找出缺省的这个数。

拿到这个题，会用很多想法，罗列几种。

（1）、在时间复杂度为O(N^2)的情况下用双重循环找出，空间复杂度为O(N)。

（2）、用哈希法，时间复杂度为O(N)，需额外空间，空间复杂度为O(N)。

（3）、先求出1到n的累加和，然后减去数组中所有数的累加和，得所求。时间复杂度为O(N)，不需额外空间。

（4）、先求出1到n的异或和，然后再跟数组中所有数的异或和，得所求。时间复杂度为O(N)，不需额外空间，由于异或运算由于加法运算，所以方法4更高效。

#include
  
   
using namespace std;

//亦或
int find_That_One1(int da[],int n,int up)
{
	int sum=0;
	for(int i=1;i<=up;i++)
		sum^=i;
	for(int i=0;i
   
    
 
    
 
    
 
    
2.一个整形数组除一个数只出现一次外，其余的都出现2次，求这个数。
 





 
    
 这里的一次可以改成奇数次，2次可以改成偶数次。这是个抑或运算的典型试题，将所有数进行异或运算即得所求。
 
    
 
    
#include
     
      
using namespace std;

int find_One(int da[],int n)
{
	int sum=0;
	for(int i=0;i
       
       
 
       

 
 
       
 
       
3.一个整形数组除两个数只出现一次外，其余的都出现2次，求这两个数。
 
 
       
 这是个抑或运算的典型试题，将所有数进行异或运算即得所求。由于出现一次的数不相同，所以其异或值不为0,。可以根据其中某一位为1将这两个数分到不同的组中，然后用方法2求解。异或值在某位为1对应那两个数在该位上不相等，自然想到分组。我选用确定最右边为0位，a&（~a+1）.
 
       

       
#include
        
         
using namespace std;

int find_One(int da[],int n)
{
	int sum=0;
	for(int i=0;i
         
          
 
          
 
          
 
          
 
          
 
          
4.一个整形数组除3个数只出现一次外，其余的都出现2次，求这3个数。
 
 3个数应该想法设法转化成2个数，然后求解。可以先求出所有数的异或值sum，即3个只出现1次的不相同的数的异或值。假设3个数为a,b,c。然后将sum与所有的数进行异或运算，得b^c,a^c,a^c。由于b^c,a^c,a^c3个新数的异或值为0,且两两互不相等同时不为0。所以必定存在在某些位上两个位1，拎一个为0，可以据此求出一个，进而转化成问题3.为了方便，首先考虑最低位。
          
#include
           
            
using namespace std;

int find_One(int da[],int n)
{
	int sum=0;
	for(int i=0;i
            
             
 求解过程中可能有错或不合理的地方，请高人斧正！