## 神奇的異或 異或如果運用得當，處理有些問題會事半功倍。 異或，英文為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; } ~~~