題目：數(shù)組中有三個(gè)數(shù)只出現(xiàn)一次，其它的數(shù)恰好出現(xiàn)兩次，找出這三個(gè)數(shù)。
先考慮“只有兩個(gè)數(shù)出現(xiàn)一次”的情況：可以找到一種方法，將數(shù)組劃分為兩部分，且讓這兩個(gè)數(shù)分別在不同部分，這樣每部分所有數(shù)的異或值，恰好分別等于這兩個(gè)數(shù)。一種簡(jiǎn)單的分法就是，先計(jì)算出這兩個(gè)數(shù)的異或值M（等價(jià)于求數(shù)組中所有數(shù)的異或值），求出M值的二進(jìn)制表示中的最低位1（其它位的1也可以，只不過(guò)麻煩點(diǎn)）在 +k位，然后根據(jù) +k位是否為1，將原數(shù)組分為兩部分。
回到原題，假設(shè)這三個(gè)不同的數(shù)是：A、B、C，它們的異或值 X = A xor B xor C，X值可能為0，也可能不為0。當(dāng)X值不為0時(shí)（比如：這三個(gè)數(shù)為3、5、7，X值為1），很難找到一種方法，將原來(lái)的數(shù)組劃分為兩部分，使得這三個(gè)數(shù)不都在同一部分。因而，要先對(duì)原來(lái)的數(shù)組進(jìn)行一次替換：將每個(gè)數(shù)與X進(jìn)行異或。這樣原來(lái)的三個(gè)數(shù)就變成了：
B xor C、A xor C、A xor B。記a = B xor C、b = A xor C、c = A xor B。新的異或值 x = a xor b xor c = 0。
由于A、B、C互不相等，顯然它們間的異或值a、b、c都不為0，且互不相等。（若a等于b，則 0 = a xor b = (B xor C) xor (A xor C) = A xor B != 0自相矛盾）
若三個(gè)數(shù)的異或值為0，且其中一個(gè)數(shù)在 +n位（n為任意值）上為1，則另兩個(gè)數(shù)在 +n位上必然一個(gè)為1，另一個(gè)為0（不然的話，這三個(gè)數(shù)的異或值就不會(huì)為0），因而根據(jù) +n位為1，可以將這三個(gè)數(shù)分成兩部分。
設(shè)f(x)為x的二進(jìn)制表示中最低位1的位置，則f(a)、f(b)、f(c)這三個(gè)數(shù)中有且只有兩個(gè)數(shù)相等。證明：不妨設(shè)f(a)、f(b)、f(c)中最小的是f(a)，k = f(a)，則b、c在 +k位上必然是一個(gè)為1，一個(gè)為0，不妨設(shè)b在 +k位為1，則根據(jù)f(x)的定義以及f(a)最小，可得f(b)等于f(a)，f(c)大于f(a)。因而，新數(shù)組的數(shù)x對(duì)應(yīng)的所有f(x)的總異或值等于f(c)。
假設(shè)f(a)等于f(b)，m = f(c)，由于c在 +m位上為1，不妨設(shè) b在 +m位也為1，則a在 +m位為0。根據(jù) +m位是否為1，可將新數(shù)組分為兩部分，每部分的異或值恰好都是 a = B xor C，可以求出數(shù)A（等于a xor X）。 將數(shù)A放入原來(lái)的數(shù)組，問(wèn)題轉(zhuǎn)為“只有兩個(gè)數(shù)出現(xiàn)一次”的情況，利用前面提到的方法算出另兩個(gè)數(shù)。總共需遍歷數(shù)組4次。
代碼：
#include <cstdio>
#include <cassert>
static inline int extract_rightmost_one(unsigned value) { return value & -value; }
// if a != b, m = extract_rightmost_one(a), n = extract_rightmost_one(b),
// k = extract_rightmost_one(a ^ b)
// then m == n != k or m == k != n or n == k != m
void print_three_unique_number(const int arr[], unsigned len)
{
assert (len >= 3 && len % 2);
const int* const beg = arr;
const int* const end = arr + len;
int xor3 = 0;
for (const int* p = beg; p != end; ++p) xor3 ^= *p;
int flag1 = 0;
for (const int* p = beg; p != end; ++p) flag1 ^= extract_rightmost_one(*p ^ xor3);
assert(flag1 != 0 && (flag1 & (flag1 - 1u)) == 0u); // flag1 == 2^^k
int xor2 = 0;
for (const int* p = beg; p != end; ++p) {
const int value = *p ^ xor3;
if (value & flag1) xor2 ^= value; //or:
// if ((value & flag1) == 0) xor2 ^= value;
}
const int number1 = xor2 ^ xor3;
const int flag2 = extract_rightmost_one(xor2);
int number2 = (number1 & flag2) ? number1 : 0; // put number1 into the array
for (const int* p = beg; p != end; ++p) {
if (*p & flag2) number2 ^= *p;
}
const int number3 = xor2 ^ number2;
printf("%d %d %d\n", number1, number2, number3);
}
上面的代碼并不嚴(yán)格符合C++標(biāo)準(zhǔn)，而是假定機(jī)器采用補(bǔ)碼表示負(fù)數(shù)（不采用補(bǔ)碼表示的老古董，一般人也碰不到）。 另外要特別注意的是，一些計(jì)算最好先轉(zhuǎn)為無(wú)符號(hào)數(shù)，避免溢出，最后再轉(zhuǎn)回有符號(hào)數(shù)。因?yàn)闃?biāo)準(zhǔn)假定有符號(hào)數(shù)間的計(jì)算不發(fā)生溢出，當(dāng)實(shí)際上發(fā)生溢出時(shí)，就是UB行為，編譯器若進(jìn)行些激進(jìn)的優(yōu)化就得不到正確結(jié)果。