Bit Manipulation

What it is

Every integer is stored as a sequence of bits. Bitwise operators (& AND, | OR, ^ XOR, ~ NOT, <</>> shifts) operate on those bits directly, which is often faster and more memory-efficient than the equivalent arithmetic.

Core tricks

• XOR cancels duplicates — a ^ a = 0 and a ^ 0 = a, so XOR-ing every element in an array where all but one value appears twice leaves exactly the unpaired value.
• Check/set/clear a bit — n & (1 << i) checks bit i, n | (1 << i) sets it, n & ~(1 << i) clears it.
• n & (n - 1) clears the lowest set bit — used to count set bits or check if a number is a power of two (n & (n-1) == 0).
• Bitmasks as sets — an integer can represent a set of up to 32/64 booleans, letting DP over subsets use an int as the state instead of an array.

Why it's often a stretch goal

The tricks above aren't derived from a general principle the way sliding window or DP are — they're closer to a memorized toolkit. Comfort with arrays and hashing is the only real prerequisite; the rest is pattern recognition.