Geek Answers Handbook

What does the operator "^ =" do in this finding of an unpaired algorithm?

Highlight an interesting piece of code to find a single number in the list of repeating numbers (where each 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 what the ^= operator does here?

+8
javascript bit-manipulation bitwise-operators
source share
2 answers

a ^= b coincides with 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 trace one execution using the list [8, 12, 8] , for example:

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

The word duplicate is incorrect. This algorithm checks for parity. A simple but somewhat incorrect definition is "when everything has a pair." a pair ... of 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 this is the xor of all unpaired elements.

+19
source share

Like the other answers, this is bitwise XOR.

About algorythm is cool if you are sure duplicates are even counted. When the number is XOR-ed with x and later XOR-ed with x , it will return the previuos value to it. If you see 3 times in this chain that 3rd place will deceive this algorithm. In addition, if there is another value in the chain, for example:

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

the result will be (X ^ Y) , and you cannot be sure that you have one unique value or more.

+4
source share

More articles:


All Articles