260. Single Number III

Key point 1

  • a ⊕ a = 0
  • a ⊕ 0 = a
  • a ⊕ b ⊕ a = b
Because a ⊕ a = 0, the pairs of numbers will cancel each other out.
Traverse the array nums and calculate the XOR of all elements. The result will be the XOR of the two numbers that appear only once.
let these single numbers be a and b.
5(101) and 3(011) in this list, the XOR result of list is 6(110).

Key point 2

Because a and b only appear once and a ≠ b, so there must be a bit in the XOR result that is 1.
The XOR result of list is 6(110), this bit is 1 number a is 5(101), this bit is 0 number a is 3(011), this bit is 1
We call the rightmost position with a 1 the rightmost set bit.
To find the rightmost set bit in the XOR result, we can use the two's complement set_bit = xor & -xor. The expression xor & -xor isolates the rightmost set bit in xor. Here, -xor is the two's complement representation of xor.

Key point 3

Traverse the list again, using the rightmost set bit to divide the list. One group has 0 at this position, and the other has 1 at this position. Number a and number b must be divided into different group.
Now, the problem is simplified to . Just calculate the XOR of all elements of tow groups.