# XOR: key points for algo IV

• usage: swap two int variables. I think the “minus” trick is easier to understand
• usage: doubly-linked list … MLP-sg connectivity java IV#2
• usage: ‘1’ XOR an unknown bit among neighboring bits => TOGGLE the bit
• usage: If you apply an all-1 toggle (bit vector), you get the “bitwise NOT” also known as “one’s complement”
• Like AND, OR, this is bitwise meaning each position is computed independently — nice simplicity

If you are looking for a one-phrase intro to the 2-input XOR, consider

) TOGGLE ie toggle the selected bits. If you apply a toggle twice, you get the original.
) DIFFERENCE ie difference gate, as a special case of “odd number of ONEs
…. Therefore, order doesn’t matter. See note below

— how about a bunch of bits to XOR together?

Wikipedia points out —  A chain of XORs — a XOR b XOR c XOR d (and so on) — evalutes to ONE iFF there is an odd number of ONEs in the inputs. Every pair of toggles would cancel out each other.

### Again, you are free to reshuffle the items as order doesn’t matter.

is the Venn diagram for a xor b xor c. Red means True. Each of the three circles were initially meaning if you shoot dart inside the ‘a’ circle, then you get ‘a=True’. If outside the ‘a’ circle, then ‘a=False’. You can see that your dart is red (i.e. True) only when encircled an odd number of times. Note your dart is unable to land outside the big circle.

Insight — iFF you toggle a NULL (taken as False) odd times, it becomes True. Therefore, if among N input bits, count of True (toggles) is odd, then result is True.

Does order of operand matter? No

https://leetcode.com/problems/single-number/ has a O(1) time O(1) space solution using this hack. Applicable on a collection of floats, or dates, or any serializable objects.