Bit Manipulation Capstone Practice

May 2026 · 32 min read

The final step is mixed practice. Real interviews and contests do not announce "use lowbit" or "this is SOS DP." Your job is to recognize the pattern from constraints, operations, and edge cases.

How to Practice

1. Read the statement and write down the bitwise operation involved.
2. Identify whether the problem is about one value, a pair, a subset, a range, or all masks.
3. Estimate constraints and map them to the catalog.
4. Solve first, then compare with a second approach if one exists.
5. Write down the invariant in one sentence.

Level 1: Interview Fundamentals

Level 2: Interview Mediums

Level 3: Core Competitive Programming

Level 4: Advanced CP

Final Cheat Sheet

x & -x                  // isolate lowest set bit
x & (x - 1)             // clear lowest set bit
x ^ y                    // differing bits / parity difference
pref[r+1] ^ pref[l]      // range XOR
for (sub=m; sub; sub=(sub-1)&m) // enumerate submasks
dp |= dp << w            // bitset subset sum
x ^ (x >> 1)             // binary to Gray
ans = max(ans, ans ^ basis[b]) // maximize XOR with linear basis

Completion Standard

You are ready for bit manipulation in interviews if you can explain the invariant for every Level 1 and Level 2 problem without memorizing code. You are ready for serious CP if you can also choose between binary trie, linear basis, SOS DP, FWT, and bitset optimization from constraints alone.