Bit Manipulation Patterns

# Bit Manipulation Patterns

This file lists all commonly used bit manipulation patterns for DSA problems, along with typical problem types, keywords, and notes on how to detect and apply each pattern. Once internalized, these cues should immediately tell you which approach to use based on the input and question keywords.

---

Pattern Table (Simplified & Prioritized)

Pattern / Category	Typical Question Types	Keywords	Notes / Scope / Rarity
XOR Patterns – Very Common (Arrays, Graphs, DP)	Single number, Pair XOR, Subarrays	XOR, unique, subset	Cancel duplicates using XOR; prefix XOR for subarrays; universal usage
Count Set Bits / Parity – Very Common (Math, Arrays)	Count 1s, Odd/even numbers	bits, set bits, parity	Use Brian Kernighan’s algorithm; O(log n) per number; universal math/array
Power of Two Checks – Common (Math, Arrays)	Check if number is power of two	n & (n-1), power	O(1) check using bitwise AND; frequent in constraints
Left / Right Shift Tricks – Common (Math, Arrays)	Multiply/divide by powers of 2	<<, >>	Efficient arithmetic; often replaces multiplication/division
Bitmask for Subsets / Combinations – Rare / Bonus (Arrays, Strings, DP)	Subset generation, Constraints	mask, subset	Encode subset selection as bits; iterate over all masks; used in combinatorial DP
XOR Graph Problems – Rare / Bonus (Graph only)	XOR path problems, special constraints	XOR, path, edges	Use XOR along paths; often combined with DP or bitmask; graph-specific

---

Bit Manipulation – Detection & Usage Guide

Rarity Legend:

• Very Common – Appears in almost every interview or coding contest; must know perfectly.
• Common – Appears frequently; good to know for typical problems.
• Rare / Bonus – Appears occasionally or in advanced/combinatorial problems.

---

1. XOR Patterns – Very Common

When to use / Detection cues:

• Input: Array or sequence of integers.
• Keywords: XOR, unique, subset.
• Problem hints: Find the single non-repeating element, XOR of pairs, subarray XOR = k.
• Why it works: XOR of a number with itself cancels to 0; XOR is associative; prefix XOR for subarrays.

Typical questions: Single non-repeating number, Count subarrays XOR=k, Two numbers with XOR=target. Mental trigger: “XOR” + “unique/single” → XOR Pattern.

---

2. Count Set Bits / Parity – Very Common

When to use / Detection cues:

• Input: Integer numbers, usually small/moderate size.
• Keywords: bits, set bits, parity, odd/even.
• Problem hints: Count number of 1s, determine parity of number.
• Why it works: Use Brian Kernighan’s algorithm (n & (n-1) removes the rightmost set bit); O(log n) per number.

Typical questions: Count 1s in integer array, Check parity of a number, XOR parity checks. Mental trigger: “Bits” + “count 1s / parity” → Count Set Bits / Parity.

---

3. Power of Two Checks – Common

When to use / Detection cues:

• Input: Single integer.
• Keywords: n & (n-1), power, check.
• Problem hints: Constraint requires number to be a power of two, or check validity for combinatorial division.
• Why it works: A number is power of 2 if it has exactly 1 bit set. n & (n-1) == 0.

Typical questions: Check if number is power of two, Validate constraints in array problems. Mental trigger: “n & (n-1)” → Power of Two check.

---

4. Left / Right Shift Tricks – Common

When to use / Detection cues:

• Input: Integer numbers.
• Keywords: <<, >>, multiply/divide by 2.
• Problem hints: Need fast multiplication or division by powers of 2, or bitwise operations.
• Why it works: Shifting left multiplies by 2, shifting right divides by 2; more efficient than arithmetic operators.

Typical questions: Multiply/divide integers by powers of 2, Optimize loops involving powers of 2. Mental trigger: “<< / >>” → Multiply/divide by powers of 2.

---

5. Bitmask for Subsets / Combinations – Rare / Bonus

When to use / Detection cues:

• Input: Array or set, small n (≤20).
• Keywords: mask, subset, combination, constraints.
• Problem hints: Generate all subsets or combinations efficiently; solve DP problems with subset states.
• Why it works: Each bit represents inclusion/exclusion of an element; iterate through 0..2^n-1.

Typical questions: Subset sum variations, combinatorial constraints, DP over subsets. Mental trigger: “mask” + “subset / combination” → Bitmask DP.

---

6. XOR Graph Problems – Rare / Bonus

When to use / Detection cues:

• Input: Tree or graph with weights.
• Keywords: XOR, path, edges.
• Problem hints: Find XOR along paths, constraints on XOR values between nodes.
• Why it works: Use XOR properties (associative and commutative) combined with DP or DFS on graph.

Typical questions: XOR of path weights, Max XOR path in tree, Special constraints on node values. Mental trigger: “XOR” + “graph/path” → XOR Graph.