Masks, XOR tricks, and the low-level questions in systems-leaning interviews.
3 questions in Data Structures & Algorithms.
XOR-folding the array leaves the unpaired value because a^a is 0 and XOR is commutative and associative, giving O(n) time and O(1) space under a precondition worth stating. That specific trick is narrow; masks used as integer sets are the part of bit manipulation that earns real work.
Count, for each of the 32 bit positions, how many numbers have that bit set, and keep the count modulo 3. Tripled values contribute multiples of 3, so the bits with a remainder belong to the single number. Setting bit 31 makes a Java int negative, so negative answers come out right in O(32n) time and constant space.
Shifting and masking works only if the shift does not sign-extend, so a signed right shift on a negative value never terminates. Either shift with the unsigned operator or clear the lowest set bit with n and n minus 1, which terminates for every input including the minimum value.