異或運算在算法中的經(jīng)典運用

比如首先排序、然后在查找不同的數(shù)據(jù)就能找到這兩個數(shù)字，這種實現(xiàn)方法的時間復(fù)雜度應(yīng)該是在O(NlgN)，因為比較排序的算法最好的時間復(fù)雜度就是這樣。但是乍一看，這題就解決了，但是還沒有充分運用一個條件，絕大多數(shù)元素是成對出現(xiàn)的，這個條件的作用是什么呢？ 當(dāng)然還有的思路就是hashmap實現(xiàn)，這種實現(xiàn)方法就是采用hash表存儲每個變量的次數(shù)，最后遍歷hash表即可，但是這種方法也存在問題，如果存在負數(shù)，或者數(shù)組元素的值特別大，采用Hashmap實現(xiàn)的空間復(fù)雜度太大，并不是我們需要的解決方式，hashmap適合的方式是在一定范圍類的數(shù)值進行統(tǒng)計。上面這兩種方法可能是比較快速想到的。

這道題的實現(xiàn)方法很多，關(guān)鍵是找到最好的實現(xiàn)方法很難，本文就介紹采用異或運算實現(xiàn)這道題目的解法。

異或運算是C語言中位運算的一種操作，這種操作對于嵌入式程序員可能比較熟悉，但是對于一般的程序員可能運用的比較少，異或操作具有如下的特征：

0^num = num; 1^num = ~num; num ^ num = 0; 其中num = 0或者1。

運用結(jié)合律等特征有：

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,則是不成立的。

從上面的結(jié)合律可以知道如果兩個相同的數(shù)進行異或操作結(jié)果是0，根據(jù)題目中元素是成對出現(xiàn)的，可以充分運用異或操作的結(jié)合特性，數(shù)組元素異或以后的結(jié)果肯定會包含兩個不成對元素的特征。

假設(shè)數(shù)組元素為a[N],其中N的值很大，不成對的元素為an,am。實現(xiàn)上述過程的步驟如下所示：

首先，變量元素對所有元素進行異或操作，得到的結(jié)果肯定是an^am。也就說通過異或操作以后，結(jié)果中保存了an和am的特征。由于am和an不同，am^an的結(jié)果肯定是大于等于1。am和an不同，那么am^an中為1的某一個bit肯定是am或者an中某一個的特征。

然后，定義兩個值num1，num2，分別用來計算an、am，選擇am^an中的某一個bit作為特征位，假設(shè)是第K位是特征位，再次對元素進行遍歷，如果元素的第K位是1，這個元素可能是am或者an，那么將當(dāng)前元素與num1進行異或操作，如果元素的第K為不為0，那么這個元素則可能是另一個值，那么將當(dāng)前元素與num2進行異或操作。這樣遍歷完所有元素，因為大部分數(shù)據(jù)成對出現(xiàn)，根據(jù)異或運算的特征，num1，num2就分別保存了兩個不同的值。

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

代碼實現(xiàn)如下：

#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];
}
/*得到第一個數(shù)*/
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;
}

上面的代碼基本上實現(xiàn)了上面的描述。

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

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

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

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