Bit Manipulation

Every integer is a row of bits, and the operators AND, OR, XOR, NOT and shifts let you read, set, clear and flip those bits directly in constant time.

Because x ^ x = 0 and x ^ 0 = x, XOR-ing a list makes every pair cancel out, which finds unique or missing values in O(n) time and O(1) space.

A set of up to about 20 items can be written as one integer where bit i means item i is included, so counting from 0 to 2^n - 1 walks through every subset.

x & (x - 1) clears the lowest set bit, which gives a fast way to count 1 bits, test for powers of two and reuse earlier answers to count bits for every number up to n.

When the state of a DP must remember which of up to about 20 items are already used, store that set as a bitmask, turning n! orderings into about 2^n states.