What is the XOR trick for finding the single number?

XOR, or exclusive or, has three useful properties: any number XOR itself equals zero, any number XOR zero equals itself, and XOR is commutative and associative. To find the single number in an array where every other number appears twice, XOR all elements together. The duplicate pairs cancel out to zero, leaving only the single number. This runs in O of n time and O of one space. For the variant where one number appears once and all others appear three times, XOR alone does not work, and you need bit counting where you count the number of ones at each bit position modulo three.