Oct-26-2020, 06:30 AM
Thanks for the clear and elaborate explanation.
(Oct-26-2020, 04:09 AM)deanhystad Wrote: A number XOR itself is zero, and a number XOR with zero is the number.
3 ^ 3 == 0 and 3 ^ 0 == 3, therefore (3 ^ 3) ^ 3 == 3.
If we sort the numbers and put them in groups:
[1,2,3,1,2,3,1] == [1,1,1,2,2,3,3] == [[1,1,1], [2,2], [3,3]]
It should be easy to see that.
1^1^1 == (1^1)^1 == 0^1 == 1
2^2 == 0
3^3 == 0
And that:
(1^0)^0 == 1^0 == 1
Another way to think about this is to group numbers into pairs knowing that the XOR
of each pair is zero:
1,2,3,1,2,3,1] = [1,1,1,2,2,3,3] = [[1,1], [1], [2,2], [3,3]] == [0, 1, 0, 0]
(0^1)^(0^0) == 1^0 == 1
The pairs cancel each other out!
But does this hold true if the numbers are placed in a different order? Think of the bits as a row of switches. All switches start off (0). When you XOR a number you toggle the switches associated with the bits that are set (1) in the number.
The switches that are flipped an odd number of times end up being on (1), and the switches flipped an even number of times end up being off (0). Looking at the example it should be obvious that the order of the numbers does not affect how many times each switch is flipped.
Output:switch Number 0000 0110 0^6 = 6 0110 0011 (0^6)^3 = 5 0101 0110 ((6^2)^3)^6) = 3 0011 flipped 0231
This is bad code. It is certainly clever, and it does a good job starting a conversation about XOR and maybe leading to deeper understanding, but it is bad code. Good code requires thinking to write, but once written it should be very easy to understand.
This code is also bad because it is not flexible. This code only works if there is one number in the list that appears an odd number of times. This same logic cannot be used as the foundation for a function that returns a list of all numbers that appear in a list an odd number of times.
Finally this code is bad because it quietly gives a bad result if the list does not meet all the requirements. Look what happens if if there are more than one number that appears an odd number of times:
[1,1,2,2,2,3,3,3] == [[1,1],[2,2],[2],[3,3],[3]] == [0,0,2,0,3] == 2^3 == 1 # What?
If there is supposed to only be one number that appears an odd number of times and two or more numbers appearing and odd number of times is an error, I would prefer the code raises an exception instead of giving me a nonsensical number.