Bit Operations

Here are the bit operations you'll use constantly. Memorize these patterns:

Check if bit i is set: (mask >> i) & 1
Set bit i: mask | (1 << i)
Clear bit i: mask & ~(1 << i)
Toggle bit i: mask ^ (1 << i)
Count set bits: popcount(mask)
Lowest set bit: mask & (-mask)
Clear lowest set bit: mask & (mask - 1)

Each operation runs in $O(1)$. The expression $1 << i$ creates a number with only bit $i$ set. OR sets bits, AND with complement clears them, XOR toggles them.

Practice until these feel automatic. In contests, you will write them dozens of times. Fumbling with bit manipulation wastes precious minutes and invites subtle bugs.