異或運算在算法中的經典運用

比如首先排序、然后在查找不同的數據就能找到這兩個數字，這種實現方法的時間復雜度應該是在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就分別保存了兩個不同的值。

由上面的分析可知，這種算法只需要遍歷兩次數組空間即可實現數據的判定，這樣時間復雜度為O(N),同時因為沒有hashmap之類的結構體，這樣空間復雜度就是O(1)。這種算法的實現肯定是最佳的。相比前面提到的hashmap、排序算法時間復雜度和空間復雜度都要小，因此這種算法的實現應該是最佳的。

代碼實現如下：

#include
#include

int whichbitone(int in)
{
int i = 0;

while((in & (1 << i)) == 0)
i ++ ;

return i;
}

int isbitone(int in, int k)
{
if((in & (1 << k)) != 0)
return 1;
else
return 0;
}

void xortest(int *array, int size)
{
int dxor = 0, xor = 0;
int i = 0, j = 0;
int num1 = 0, num2 = 0;

for(i = 0; i < size; ++ i)
dxor ^= array[i];

if(dxor != 0)
{
j = whichbitone(dxor);
for(i = 0; i < size; ++ i)
{
if(isbitone(array[i],j) == 1)
num1 ^= array[i];
else
num2 ^= array[i];
}
/*得到第一個數*/
printf("first data is %d",num1);
printf("second data is %d",num2);
}
}

int main(int argc, char *argv[])
{
int array[10] = {1,2,3,4,7,2,3,1,4,9};
xortest(array,10);

return 0;
}

上面的代碼基本上實現了上面的描述。

對于本題的另一個變換“數組中元素成對出現，但是存在三個不成對的元素，如何快速的找出這三個元素？”

這個題看起來和本題有一定的聯系性，甚至我認為我們可以采用相同的方法找出三個值，但是后來發現這種方法存在一個問題，但是三個的情況要遠遠比兩個的復雜，因為其中存在的可能性要多很多，不是不是屬于這個元素就是另一個元素的問題，雖然這種解法可能導致問題產生，但是還是有可能解決的，除了當三個元素的異或結果為0，即x^y^z = 0時，這種方法是不成立的。
對于三個不同元素的找份，我認為主要是找到其中的一個元素，然后將這個元素移除，在進行上述的另外兩個元素尋找。當然我們首先排除三個數據異或為零的特殊情況。具體的實現可以參考http://blog.csdn.net/zzran/article/details/8108787。

還是存在這個問題，如果這三個元素異或以后的值剛好為零，這種方法不能解決了，因此采用異或解決只有一個不成對或者兩個不同元素的問題是沒有問題的，對于三個元素具有一定的可行性，但是不一定時時成立。

異或運算在算法中針對的問題也是特定的，主要是這種元素成對出現的問題，如果不成對出現，這種算法的實用性能會大大的降低，即使是重復元素都不一定是實用的。