## 神奇的异或 异或如果运用得当，处理有些问题会事半功倍。 异或，英文为exclusive OR，或缩写成xor 异或(xor)是一个数学运算符。它应用于逻辑运算。异或的数学符号为"⊕"，计算机符号为"xor"。其运算法则为: a⊕b = (¬a ∧ b) ∨ (a ∧¬b) 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。 运算法则折叠 1. a ⊕ a = 0 2. a ⊕ b = b ⊕ a 3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c; 4. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c. 5. a ⊕ b ⊕ a = b. ### 异或的运用 1.判断两个数是否相等。若a^b==0 则a=b，否则a！=b 2.交换两个数的值。a=a^b;b=a^b;a=a^b; 3.法则1，处理整数成对问题 别人的例子：  “一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字？”这是经典的算法题，乍看这个题的思路特别多。    比如首先排序、然后在查找不同的数据就能找到这两个数字，这种实现方法的时间复杂度应该是在O(NlgN)，因为比较排序的算法最好的时间复杂度就是这样。但是乍一看，这题就解决了，但是还没有充分运用一个条件，绝大多数元素是成对出现的，这个条件的作用是什么呢？ 当然还有的思路就是hashmap实现，这种实现方法就是采用hash表存储每个变量的次数，最后遍历hash表即可，但是这种方法也存在问题，如果存在负数，或者数组元素的值特别大，采用Hashmap实现的空间复杂度太大，并不是我们需要的解决方式，hashmap适合的方式是在一定范围类的数值进行统计。上面这两种方法可能是比较快速想到的。    这道题的实现方法很多，关键是找到最好的实现方法很难，本文就介绍采用异或运算实现这道题目的解法。    异或运算是C语言中位运算的一种操作，这种操作对于嵌入式程序员可能比较熟悉，但是对于一般的程序员可能运用的比较少，异或操作具有如下的特征：    0^num = num; 1^num = ~num; num ^ num = 0; 其中num = 0或者1。    运用结合律等特征有：    a^a^b^b^c = (a^a)^(b^b)^c=0^0^c=c;    需要注意：如果有a + b = c; 则有可能使得a ^ b ^ c = 0;这个条件是非充分非必要，比如a = 1，b = 2， c = 3，这时候的a ^ b ^ c = 0是成立的，但是a = 2, b = 2, c = 4,则是不成立的。    从上面的结合律可以知道如果两个相同的数进行异或操作结果是0，根据题目中元素是成对出现的，可以充分运用异或操作的结合特性，数组元素异或以后的结果肯定会包含两个不成对元素的特征。    假设数组元素为a[N],其中N的值很大，不成对的元素为an,am。实现上述过程的步骤如下所示：    首先，变量元素对所有元素进行异或操作，得到的结果肯定是an^am。也就说通过异或操作以后，结果中保存了an和am的特征。由于am和an不同，am^an的结果肯定是大于等于1。am和an不同，那么am^an中为1的某一个bit肯定是am或者an中某一个的特征。    然后，定义两个值num1，num2，分别用来计算an、am，选择am^an中的某一个bit作为特征位，假设是第K位是特征位，再次对元素进行遍历，如果元素的第K位是1，这个元素可能是am或者an，那么将当前元素与num1进行异或操作，如果元素的第K为不为0，那么这个元素则可能是另一个值，那么将当前元素与num2进行异或操作。这样遍历完所有元素，因为大部分数据成对出现，根据异或运算的特征，num1，num2就分别保存了两个不同的值。 异或的运算（增大数）： ~~~ **ZOJ Problem Set - 3870** Team Formation Time Limit: 3 Seconds Memory Limit: 131072 KB For an upcoming programming contest, Edward, the headmaster of Marjar University, is forming a two-man team from N students of his university. Edward knows the skill level of each student. He has found that if two students with skill level A and B form a team, the skill level of the team will be A ⊕ B, where ⊕ means bitwise exclusive or. A team will play well if and only if the skill level of the team is greater than the skill level of each team member (i.e. A ⊕ B > max{A, B}). Edward wants to form a team that will play well in the contest. Please tell him the possible number of such teams. Two teams are considered different if there is at least one different team member. Input There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case: The first line contains an integer N (2 <= N <= 100000), which indicates the number of student. The next line contains N positive integers separated by spaces. The ith integer denotes the skill level of ith student. Every integer will not exceed 109. Output For each case, print the answer in one line. Sample Input 2 3 1 2 3 5 1 2 3 4 5 Sample Output 1 6 ~~~ 该题大概要求一系列数中，异或结果大于原来两个数的最大值。 分析： 对于两个正整数a和b，设a的高位1为x，b的高位1为y。判断是否有a^b>max(a,b) 若x=y，a^b<max(a,b) 若x!=y，若x<y，显然a<b,如果b中x位为0异或的结果会比b还大，如果b中x位为1异或的结果会比b还小。若x>y，也一样。也就是说，一个大数和小数异或，小数的高位1的位置对应大数位为0的话，那么这两个数就满足条件。 于是我们可以所有高位1的数量统计起来，遍历每一个数，寻找该位的高位1的位置，之后寻找所有的0位，查询对应位置高位1是否有数，有就加起来。 源码： ~~~ #include<iostream> using namespace std; int num[100000]; int bit[32]; //寻找1的高位位置 int findHigh1(int x){ int h=31; while(h>=0){ if(x&(1<<h)){ bit[h]++; break; } h--; } return h; } //寻找比x大的数有多少个 int findNum(int x){ int h=31; while(h>=0){ if(x&1<<h){ break; } h--; } int tcount=0; while(h>=0){ if(!(x&1<<h)){ tcount+=bit[h]; } h--; } return tcount; } int main(){ int t,n,i,j,a,in,count; while(cin>>t){ while(t>0){ cin>>n; count=0; for(i=0;i<32;i++){ bit[i]=0; } for(j=0;j<n;j++){ cin>>num[j]; findHigh1(num[j]); } for(j=0;j<n;j++){ count+=findNum(num[j]); } cout<<count<<endl; t--; } } return 0; } ~~~