What does the "^=" operator do in this find non-paired number algorithm? [duplicate]

Question

Saw an interesting piece of code to find a lonely number in a list of duplicate numbers (where every number in the list occurs twice except for one).

function findNonPaired(listOfNumbers) {
  let nonPairedNumber = 0

  listOfNumbers.forEach((n) => {
      nonPairedNumber ^= n
  })

  return nonPairedNumber
}

const x = [1,5,4,3,9,2,3,1,4,5,9]
console.log(findNonPaired(x))

This solution looks very elegant, but I'm curious at to what the ^= operator is actually doing here?

Answer 1

a ^= b is the same as a = a ^ b where ^ is the bitwise XOR operator.

0 ^ 0 === 0
1 ^ 0 === 1
0 ^ 1 === 1
1 ^ 1 === 0

This is a neat algorithm. Let's trace one execution with the list [8, 12, 8] for example:

0 ^ 8 = 0000 ^ 1000 = 1000
        1000 ^ 1100 = 0100
        0100 ^ 1000 = 1100 = 12

The word "duplicate" isn't correct. This algorithm tests for parity. A simple but somewhat wrong definition is "when everything has a pair". pair...parity.

[2,2,2,3,3,5,5,5,5] will return 2 because everything else has a pair.

[3,4,5] will actually return 2 (011^100^101 -> 010) because that is the xor of all the unpaired items.

Answer 2

Like other answers say - it is a bitwise XOR.

About the algorythm - it is cool if you are sure that the duplicates are even count. When a number is XOR-ed with x and later again XOR-ed with x it will return to it's previuos value. If one number is seen 3 times in this chain, the 3-rd occurence will fool this algorythm. Also if there is one more value that is single in the chain, like:

a, b, c, X, a, c, b, Y

the result will be (X ^ Y) and you can't be sure if you have one unique value or more.