Explain this use of XOR in this function?

Question

I saw this piece of code that was used to solve ol "Find one number in an array that does not have a duplicate." question. I looked at this for a while this morning, but I can’t cover for sure how this is done.

I don’t understand how k always ends up holding a non-duplicate value. Can anyone explain how this works?

static void Main(string[] args) { int[] list = { 3,6,9,12,3,6,9 }; int k = 0; for (int i = 0; i < list.Length; i++) { k = k ^ list[i]; } Console.WriteLine(k); } 

Answer 1

It works only if only one number is not duplicated (or occurs some odd number of times), and all other numbers have an even number of times.

When you xor a number to another number twice (or any other even number of times), it cancels itself, leaving the original number.

Answer 2

It is a bit like the “Nerds, Jocks and Lockers” problem in terms of “flipping bits,” leaving certain bits to set, while others are not.

The main behavior is that A XOR B works like "(A OR B) AND NOT (A AND B)". So, 0 ^ 0 = 0, 1 ^ 0 = 1, but 1 ^ 1 = 0 (unlike OR). Now you start from zero (without bits) on K. Then you XOR this with the letter 3, which (as a byte) has bits 00000011 and assigns the result K. You end up getting 00000011 for K, because the bits that are set to literal 3, everyone is not set to K when it is 0. Now, if you again had to XOR K with literal 3, you will get 0 because all bits match between the two values, so XOR will return 0 for every bit.

This process is commutative, therefore (((((XOR 3) XOR 6) XOR 3) XOR 6) gives the same result (0) as ((((0 XOR 6) XOR 6) XOR 3) XOR 3), or almost any other combination of XORing 0 with 3 twice and 6 twice.

The end result is that, given the list of these numbers, any number that occurs twice (or an even number of times), first “XORed in” to K, and then “XORed out” the second, leaving K with its bits set to one a meaning that only once happened; 12.

Here is a twofold demonstration of the complete problem (using "nibbles" because we have no values ​​greater than 16):

 0000 0 ^^^^ XOR 0011 3 ---- = 0011 3 ^^^^ XOR 0110 6 ---- = 0101 5 ^^^^ XOR 1001 9 ---- = 1100 12 ^^^^ XOR 1100 12 ---- = 0000 0 <-this is coincidence; it'd work the same regardless of the unduped value ^^^^ XOR 0011 3 ---- = 0011 3 ^^^^ XOR 0110 6 ---- = 0101 5 ^^^^ XOR 1001 9 ---- = 1100 12 <- QED 

EDIT FROM COMMENTS:. Although this answer works for the specific question asked, even the smallest change in the problem will lead to a "violation" of this implementation, for example:

• The algorithm does not completely correspond to a zero number ; thus, the algorithm cannot determine the difference between a null value as the only unpaired value and no unpaired values ​​at all.
• The algorithm works only for pairs, not for triplets . If 3 happened three times and was still a "trick", and 12 was still the correct answer, this algorithm would actually return 15 (1100 ^ 0011 == 1111), which are not even on the list.
• The algorithm only works if there is only one non-duplicated value in the list ; if 8 and 12 were both unpaired values ​​that are expected to be returned, the algorithm will return an XOR of two (1100 ^ 1000 == 0100 == 4)

An efficient algorithm could be developed that would return the correct answer in all these cases in addition to the original case, but most likely it would not include XOR.

Answer 3

Any number can be expressed as a sequence of bits:

 3 == 0...00011 6 == 0...00110 9 == 0...01001 

If you XOR them twice, switching bits will cancel each other out.

Therefore, if one number appears in the list once (or an odd number of times), it will be the only one whose bit remains "non-decoupled".

Answer 4

keithS is in place, but it may be a little easier to follow.

The simplest explanation I can come up with is related to the four properties of XOR:

• 0 XOR x = x, for any number x
• x XOR x = 0, for any number x
• XOR is commutative: x XOR y = y XOR x (this allows you to rebuild a series of XOR operations as you see fit)
• XOR is associative: (x XOR y) XOR z = x XOR (y XOR z) (this allows you to evaluate XOR in whatever order you think is necessary)

Using properties 2 and 3, you can change the list of input data so that all duplicates are next to each other:

{3,6,9,12,3,6,9} → {3, 3, 6, 6, 9, 9, 12};

By properties 1 and 4, we can XOR these numbers in pairs in any order, and all pairs of identical numbers become 0. After that, only the unexpanded number remains nonzero:

{0, 0, 0, 12};

Also by property 1, since k starts from zero, and all repeating numbers have XOR'ed to become zero, all that remains is 12

Answer 5

This works because the XOR operator is commutative and associative . This means that you can change the conditions in any order:

 a ^ b ^ c == a ^ c ^ b == c ^ a ^ b == ... (etc.) 

This works for strings of any length. Therefore:

 3 ^ 6 ^ 9 ^ 12 ^ 3 ^ 6 ^ 9 == (3 ^ 3) ^ (6 ^ 6) ^ (9 ^ 9) ^ 12 

Since x ^ x == 0 for any integer, which means that you can eliminate all pairs until you get 0 ^ 12 , which is only 12 .

Answer 6

 a ^ a = 0 a ^ 0 = a 0 ^ a = a ^ 0 a = b ^ c a = c ^ b int[] list = { 3,6,9,12,3,6,9 }; k ^ 3 k ^ 6 k ^ 9 k ^ 12 k ^ 3 k ^ 6 k ^ 9 = k ^ 3 // dupe k ^ 3 k ^ 6 k ^ 6 k ^ 9 k ^ 9 k ^ 12 // non-dupe = k ^ 12 = 0 ^ 12 = 12 

Answer 7

The code you refer to does not actually solve the problem. For example, put three lists in a list and you will get 12, although 12 is duplicated twice.

The result of the XOR is essentially whether there is an odd or even number of this bit combination. Therefore, if the list contains an odd number of 12 (be it 12 or 100 and one 12 seconds) and an even number of each other, the result will always be 12.

Worse, if there was an odd number of several different numbers in the list, the result value cannot be any of the numbers in the list . For example, one 3 and one 14 will result in 13. This is because XOR really works with bits, not integers. The XOR of 14 (1110b) and 3 (0011b) leads to 13 (1101b), because XOR sets any bits that are common between numbers to zero.

Code that actually solves the problem:

 using System.Linq; using System.Collections.Generic; ... static void Main ( string[] args) { int[] list = { 3,6,9,12,3,6,9 }; int[] nonDupes = list .GroupBy(x => x) .Where(x => x.Count() == 1) .Select(x => x.Key) .ToArray(); string output = string.Join(",", nonDupes); Console.WriteLine(output); } 

Answer 8

When using XOR, you should keep in mind that you will work with bits. In other words, you will only have 0 and 1 to deal with.

The definition of XOR is so simple:

 0 XOR 0 -> 0 0 XOR 1 -> 1 1 XOR 1 -> 0 

So, if you apply this to your code and convert 3 to 0011 , from 6 to 0110 , from 9 to 1001 and from 12 to 1100 and call the XOR method on them, as in the example below, you will get 1100 , which will represent the value 12.

An example :

  0011 XOR 0110 = 0101 -> 5 

This is not an algorithm to eliminate duplicate values. It happened by coincidence that you got 12.