題目來源：劍指offer

01 題目描述

一個數組中除了兩個數字以外，其他都出現兩次。請寫程序找出這兩個只出現一次的數字。要求時間複雜度是O(n),空間複雜度是O(1)

例如輸入數組{2,4,3,6,3,2,5,5}。只有4，6兩個數字出現了一次，所以輸出數字4，6。

02 解題

首先我們回憶一下位運算

• 與運算：1&1=1， 1&0=0, 0&0=0; 有0 結果為0，全1結果為1；
• 或運算：1 | 1 = 1， 1 | 0 = 1，0 | 0 = 0；有一結果為1，全0結果為0
• 異或運算： 1^1 = 0, 1 ^ 0 = 1, 0 ^ 0 = 0; 相同結果為0 ，不同結果為1；

那麼一個數異或它自己就是0。

如果現在題目是：數組中只有一個數字出現了一次，其他數字都出現了兩次。求只出現一次的數字。

思考下：這個時候是不是將數組中所有的數字"異或"一遍就是結果值。

接下來求解本題目

將數組中所有的值都異或一遍，得到的是兩個不相等的數值異或的結果，必定不為0。

數字不為0，那麼他的二進制中一定存在1。

如4，6異或結果 2(十進制） = 010(二進制)

2的二進制中的第二位的1。那麼4與6的二進制中"第二位"必定為不同的值

我們可以把數組中的值，按照二進制中第二位為0，或者1將數組中的值分別分為兩組。

如{2,4,3,6,3,2,5,5}轉為二進制數組{010(2),100(4),011(3),110(6)，011(3),010(2),101(5),101(5)} 分兩組

第二位為0的 {100(4)，101(5),101(5)} 異或結果為4

第二位為1的 {010(2)，011(3)，110(6),011(3), 010(2)} 異或結果為6

第二位為0的組合必定包含4，第二位為1的值必定包含6。

再將這兩組值分別異或，得到的結果即為所求。

怎麼將數組中的值分為兩組

上述4與6的異或結果是2，確定2中第一個1（從後到前）。

確定一個數值的第一個1，這個1後面的都為0。

如 2=10（二進制）。

10（二進制） & 1（二進制）= 0

10（二進制） & 10（二進制）= 10 。我們先將此時的 10(二進制)保留。

與原數組中的值做與運算，有兩種結果，一種是0。一種是不為0。通過這種方式將數組中的值分為兩組。

03 總結&代碼

總結：1.整個數組做一次異或運算，得到異或結果A

2.找到異或接過A第一個（從後往前）1的位置B。

3.用B與原數組做與運算，將數值分為兩組。

public static void findNotRepeatTwoNum(int[] arr) {
 if (arr == null && arr.length < 2) {
 return;
 }
 int xorResult = arr[0];// 1.與或運算
 for (int i = 1, length = arr.length; i < length; i++) {
 xorResult ^= arr[i];
 }
 int first1BitValue = findFirstBits1(xorResult);// 2.第一個1的位置
 int resultNum1 = 0;
 int resultNum2 = 0;
 for (int num : arr) {
 if ((first1BitValue & num) == 0) {// 3.
 resultNum1 ^= num;
 } else {
 resultNum2 ^= num;
 }
 }
 System.out.println("第一個數值 " + resultNum1 + " 第二個數值" + resultNum2);
}
public static int findFirstBits1(int xorResult) {
 int first1BitValue = 1;
 while ((xorResult & first1BitValue) == 0) {
 first1BitValue <<= 1;
 }
 return first1BitValue;
}