260. Single Number III

password

URL

type

status

date

slug

summary

tags

category

icon

### 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.