Bit manipulation

O(1)/O(n)

Treat an integer as a row of on/off bits and flip, test, or combine them with &, |, ^, ~, and shifts. A mask, a number with one bit set, targets exactly the bit you want.

Signals

find the single or unique number using XORset, clear, toggle, or test a bitpack many yes/no flags into one integercount set bits or check a power of two

Template

function findUnique(nums) {
    return nums.reduce((acc, n) => acc ^ n, 0);
}
function setBit(mask, i) { return mask | (1 << i); }
function clearBit(mask, i) { return mask & ~(1 << i); }
function hasBit(mask, i) { return (mask & (1 << i)) !== 0; }

Looks similar, isn't

Hash set / map: A hash set can track which values you've seen, but it costs O(n) extra memory. When values are small flags, or every number but one appears twice, packing them into one integer and XOR-ing or masking gets the same answer in O(1) space, with no set to allocate.

values fit in a fixed 32/64-bit word, one pass over the bits or the array -> O(1) per bit trick on a single word, O(n) to XOR/mask across an array.

Learn this pattern