Bit manipulation is one of the most powerful tools in competitive programming. Many problems that look complex become simple once you “map” values, states, or conditions into bits.

This blog explains:

• What bit mapping is
• Why it is useful
• Common patterns
• Advanced tricks
• Practice problems

1. What is Bit Mapping?

Bit mapping means representing information using bits of an integer.Since an int has 32 bits and a long long has 64 bits, you can store: - Up to 32/64 boolean flags - A subset of size ≤ 20 efficiently - State compression for DP - Parity information - Frequency modulo 2 - Masks for constraints

2. Basic Representation

Representing a subset If we have a set of size n, we can represent a subset as a number: If bit i is set → element i is present.

Example:

mask = 13 Binary = 1101

This means: element 0 → present element 1 → not present element 2 → present element 3 → present

3. Basic Operations

// Check if bit i is set if (mask & (1 << i))

// Set bit i mask |= (1 << i);

// Remove bit i mask &= ~(1 << i);

// Toggle bit i mask ^= (1 << i);

4. Iterating Over All Subsets

If n ≤ 20:

for (int mask = 0; mask < (1 << n); mask++) { // process subset }

Time complexity: O(2ⁿ)

This is very common in: Subset DP Brute force optimization Meet in the middle

5. Enumerating Submasks (Very Important Trick)

This is a classic Codeforces trick:

for (int sub = mask; sub; sub = (sub — 1) & mask) { // sub is a submask of mask }

This runs in O(3ⁿ) total over all masks.

Used in: - SOS DP - Partition problems - Inclusion–exclusion

6. Bit Mapping for Parity Problems

Many problems only care about even/odd frequency. Instead of storing full frequency array, store parity in bits.

Example:

String of lowercase letters 26 letters → use 26-bit mask

int mask = 0; for (char c : s) { mask ^= (1 << (c — 'a')); }

If mask == 0 → all characters appear even times. This trick appears frequently in palindrome problems.

7. State Compression DP

Classic pattern: dp[mask] Meaning: answer when selected elements = mask.

Example problems: TSP (n ≤ 20)

Assignment problems Matching problems Transition example:

for (int mask = 0; mask < (1 << n); mask++) { for (int i = 0; i < n; i++) { if (!(mask & (1 << i))) { dp[mask | (1 << i)] = min( dp[mask | (1 << i)], dp[mask] + cost[i] ); } } }

8. Mapping Constraints Into Bits

Sometimes constraints can be represented as bitmasks. Example: Each number has certain properties (prime factors, digits used, etc.) Instead of storing full info, store: number → bitmask of properties

Then:

Check compatibility with & Merge properties with | Detect conflicts quickly

9. Bit Mapping with XOR

XOR is extremely powerful in bit problems. Properties:

a ^ a = 0 a ^ 0 = a Commutative and associative

Applications: Prefix XOR Subarray XOR problems Finding unique element Linear basis problems

10. Common Mistakes

1) Using int instead of long long If shifting beyond 31 bits → use 1LL << i

2) Forgetting operator precedence Always use parentheses:

if (mask & (1 << i)) // correct 3) TLE with 2ⁿ Only use full subset iteration when n ≤ 20.

11 Advanced Tricks

Built-in Functions __builtin_popcount(mask); // count set bits __builtin_ctz(mask); // count trailing zeros __builtin_clz(mask); // count leading zeros

For long long:

__builtin_popcountll(mask); Trick: Get Lowest Set Bit int low = mask & -mask;

Useful in: Removing bits one by one Binary indexed tricks XOR basis

12 Example Problem Patterns

You will see bit mapping in:

• Subset DP problems
• Constructive bitwise problems
• XOR based problems
• Graph coloring (small n)
• Matching problems
• Game theory state compression

13. Practice Problems

From Codeforces:

TSP style problems (search: "bitmask dp") SOS DP problems XOR subarray problems Palindrome parity problems Assignment DP

14 . When Should You Think About Bit Mapping?

Use bit mapping when: n ≤ 20 Only parity matters You need fast set operations State compression is possible Constraints can be represented as yes/no flags

15. Final Advice

Bit mapping is not just about using & and |.

It is about: Encoding information efficiently Reducing state size Turning combinatorics into binary math Recognizing hidden subset structure The more problems you solve, the more naturally you'll start seeing where masks apply.