LeetCode Single Number III：位運算找兩個單獨數字

題目大意

數組中只有兩個數字出現一次，其餘均出現兩次。線性時間、常數空間找出這兩個數字。

解法：異或分組

1. 全體異或得 xor_all = a ^ b（a, b 為目標數字）。
2. 找 xor_all 中任一為 1 的位（如 lowbit），該位上 a, b 不同。
3. 根據該位將數組分為兩組，每組內部異或即得 a 和 b。

代碼 (Java)

public int[] singleNumber(int[] nums) {
    int xorAll = 0;
    for (int n : nums) xorAll ^= n;
    int diffBit = xorAll & (-xorAll); // 取最低位 1
    int a = 0, b = 0;
    for (int n : nums) {
        if ((n & diffBit) != 0) a ^= n;
        else b ^= n;
    }
    return new int[]{a, b};
}