數組中只出現一次的數字，數組出現數字

數組中只出現一次的數字，數組出現數字

題目描述：一個整型數組裡除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。

思路:先看一個簡單的實例，若是找數組中只出現一次的一個數，其它的數都出現兩次，直接對數組元素進行位異或就可以得到數組中只出現一次的一個數。本題中，找數組中只出現一次的兩個數，則要將數組分成2個子數組，每個子數組中僅存在出現一次的一個數。關鍵就在於分組的標准，而對數組中所有的元素進行異或，得到的是這個數的異或。這個結果不為0，則一定存在某一個數字的一位為1，另一個數字中的某位為0，這樣異或的結果才不為0。因此分組的標准是對數組元素全部進行異或的結果中首位為1的那一位（假設是第N位）。然後以這個數與數組中元素進行與運算，進行分組。數組元素第N位為1的分一組，為0為另一組。在每個子數組中進行全部異或，最終可以得出數組中只出現一次的兩個數。

 1 #include "stdafx.h"
 2 
 3 unsigned int FindFirstBitIs1(int num);
 4 bool IsBit1(int num, unsigned int indexBit);
 5 
 6 void FindNumsAppearOnce(int data[], int length, int* num1, int* num2)
 7 {
 8     if(data == NULL || length < 2)
 9         return;
10     
11     int resultExclusiveOR = 0;
12     for(int i = 0; i < length ; ++ i)
13         resultExclusiveOR ^= data[i];
14     
15     unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);
16     
17     *num1 = *num2 = 0;
18     for(int j = 0; j < length ; ++j)
19     {
20         if(IsBit1(data[j], indexOf1))
21             *num1 ^= data[j];
22         else
23             *num2 ^= data[j];
24     }
25 }
26 
27 // 找到num從右邊數起第一個是1的位
28 unsigned int FindFirstBitIs1(int num)
29 {
30     int indexBit = 0;
31     while(  ((num & 1) == 0)  && (indexBit < 8*sizeof(int))   )
32     {
33         num = num >>1;
34         ++ indexBit;
35     }
36     
37     return indexBit;
38 }
39 
40 // 判斷數字num的第indexBit位是不是1
41 bool IsBit1(int num, unsigned int indexBit)
42 {
43     num = num >> indexBit;
44     return(num & 1);
45 }
46 
47 int main()
48 {
49     int data[] = {2, 4, 3, 6, 3, 2, 5, 5};
50     int length = sizeof(data) / sizeof(int);
51     
52     int result1, result2;
53     FindNumsAppearOnce(data, length, &result1, &result2);
54     
55     printf("%d  %d\n", result1, result2);
56     
57     return 0;
58 }