Topic 19 of 20
XOR tricks, masks and counting bits: short, fast solutions that impress.
Computers store integers in binary, and operating on those bits directly gives very fast solutions with O(1) extra space. The core operators are AND (&), OR (|), XOR (^), NOT (~) and the shifts (<<, >>). A few identities do most of the work: x ^ x = 0 and x ^ 0 = x (so XOR cancels out pairs), x & (x − 1) clears the lowest set bit, and x & −x isolates it.
Most interview questions here are one of three types. XOR cancellation: find the element that appears an odd number of times. Bit counting: count set bits, or build a table of counts with DP. Masks: test, set or clear the i-th bit, or treat an integer as a set of up to 32 items, which is also what bitmask DP relies on.
Be careful with signed integers and language differences. Python integers are unbounded, while Java and C++ use fixed-width two's complement, so shifts and negative numbers behave differently.
XOR cancels pairs; the most famous bit trick.
XOR of indices and values, or Gauss's sum.
Addition with XOR and carry, without '+'.
Split the numbers by one differing bit.
The AND of a range is the common binary prefix.