🚀 Bit Manipulation Roadmap (DSA + CP)

A complete README-style roadmap for Bit Manipulation, starting from foundation concepts to competitive programming level.

---

⚡ 🟢 EASY BIT MANIPULATION (Foundation Level)

Goal: Understand operators + basic tricks + build intuition

---

🔹 Core Operators (MUST KNOW)

1) AND &

Use: check bit / mask filtering Formula:

n & (1 << i)

Checks whether the i-th bit is set.

---

2) OR |

Use: set bit Formula:

n | (1 << i)

Sets the i-th bit to 1.

---

3) XOR ^ ⭐

Use: toggle / difference / unique element

Important XOR Rules

x ^ 0 = x
x ^ x = 0
x ^ y ^ x = y

---

4) NOT ~

Flips all bits.

~n

---

5) Left Shift <<

Formula:

n << k = n * 2^k

---

6) Right Shift >>

Formula:

n >> k = n / 2^k

---

🔹 Basic Bit Tricks

✅ Check Even / Odd ⭐

if(n & 1) odd
else even

---

✅ Check i-th Bit

(n & (1 << i)) != 0

---

✅ Set i-th Bit

n = n | (1 << i)

---

✅ Clear i-th Bit

n = n & ~(1 << i)

---

✅ Toggle i-th Bit

n = n ^ (1 << i)

---

🔹 Classic Problems

⭐ Check Power of 2

(n > 0) && ((n & (n - 1)) == 0)

---

⭐ Count Set Bits (Naive)

while(n){
    cnt += (n & 1);
    n >>= 1;
}

---

⭐ Remove Last Set Bit

n = n & (n - 1)

---

⭐⭐⭐ Find Single Number

ans ^= arr[i]

All duplicates cancel out.

---

⚡ 🟡 MEDIUM BIT MANIPULATION (Interview Level)

Goal: Apply XOR + masks + patterns in interview problems

---

🔹 XOR Based Problems ⭐⭐⭐

✅ Find Two Unique Numbers

Formula:

xr = a ^ b
setBit = xr & -xr

Split numbers into 2 groups using rightmost set bit.

---

✅ Missing Number

ans = 0;
for(int i=0;i<=n;i++) ans ^= i;
for(auto x:arr) ans ^= x;

---

✅ XOR from 1 to N

Pattern:

n % 4 == 0 -> n
n % 4 == 1 -> 1
n % 4 == 2 -> n+1
n % 4 == 3 -> 0

---

✅ Find Duplicate using XOR

xor(all elements) ^ xor(1..n-1)

---

🔹 Bit Counting & Tricks

⭐⭐⭐ Brian Kernighan’s Algorithm

while(n){
    n = n & (n - 1);
    cnt++;
}

Time = O(number of set bits)

---

✅ Count Bits from 1 to N

DP Formula:

dp[i] = dp[i >> 1] + (i & 1)

---

🔹 Subsets & Bitmasking ⭐⭐⭐

✅ Generate All Subsets

for(int mask=0; mask<(1<<n); mask++)

---

✅ Check Element in Subset

if(mask & (1 << i))

---

✅ Subset Sum using Bitmask

Loop through all masks and sum selected bits.

---

🔹 Range & Logic Problems

✅ Bitwise AND of Range

Repeatedly remove rightmost set bit:

while(right > left)
    right = right & (right - 1);

---

⭐⭐⭐ Maximum XOR of Two Numbers

Use Trie + bit traversal.

---

✅ Minimum XOR Pair

Sort array and compare adjacent pairs.

---

🔹 Practical Use Cases

✅ Swap Two Numbers using XOR

a ^= b;
b ^= a;
a ^= b;

---

✅ Differ by One Bit

x = a ^ b;
(x & (x - 1)) == 0

---

⚡ 🔴 HARD BIT MANIPULATION (Advanced / CP Level)

Goal: Master optimization + subset DP + advanced XOR

---

🔸 Advanced XOR & Tricks ⭐⭐⭐

✅ Trie for Maximum XOR ⭐⭐⭐

Store binary bits from MSB → LSB.

Formula idea: For each bit, try opposite bit.

---

✅ XOR Subarray Problems

Prefix XOR concept:

xr ^= arr[i]

---

✅ Count Subarrays with Given XOR ⭐⭐⭐

Formula:

prefixXor ^ k

Use hashmap frequency.

---

🔸 Bitmask DP ⭐⭐⭐

✅ Traveling Salesman Problem (TSP)

State:

dp[mask][city]

---

✅ Assignment Problem

State:

dp[mask]

---

✅ DP with Subsets

Classic formula:

dp[mask] = min(dp[mask], dp[mask ^ (1<<i)])

---

🔸 Advanced Bitmasking

⭐⭐⭐ SOS DP (Sum Over Subsets)

Formula:

for(int i=0;i<n;i++)
    for(int mask=0;mask<(1<<n);mask++)
        if(mask & (1<<i))
            dp[mask] += dp[mask ^ (1<<i)];

---

✅ Meet in the Middle

Split into two halves and use subset sums.

---

✅ Submask Iteration ⭐⭐⭐

for(int sub = mask; sub; sub = (sub - 1) & mask)

---

🔸 Mathematical Bit Tricks

⭐⭐⭐ Fast Exponentiation using Bits

while(b){
    if(b & 1) ans *= a;
    a *= a;
    b >>= 1;
}

---

✅ Binary Exponentiation Modulo

ans = (ans * a) % mod

---

🔸 Advanced Concepts

⭐⭐⭐ Gray Code

Formula:

gray = n ^ (n >> 1)

---

✅ Bitwise Convolution

Used in XOR convolution / FWT.

---

✅ Count Pairs with XOR in Range

Use Trie + bit counting.

---

🚀 FINAL PRIORITY (If Short on Time)

⭐ MUST DO TOPICS

1. XOR Basics
2. Power of 2 Check
3. Single Number
4. Brian Kernighan
5. Generate Subsets
6. Maximum XOR
7. Count Subarray XOR
8. Bitmask DP
9. Gray Code
10. Binary Exponentiation

---

🎯 FINAL GOAL PATH

📌 For Interviews

• XOR basics
• set/clear/toggle bit
• single number
• count bits
• subsets
• max XOR

📌 For Competitive Programming

• Trie XOR
• Subarray XOR
• SOS DP
• TSP
• Submask iteration
• Meet in middle

---

🏁 Master Formula Sheet

Check bit       -> n & (1<<i)
Set bit         -> n | (1<<i)
Clear bit       -> n & ~(1<<i)
Toggle bit      -> n ^ (1<<i)
Remove last set -> n & (n-1)
Power of 2      -> n&(n-1)==0
Gray code       -> n^(n>>1)

---

🔥 This roadmap is now in proper README.md format, perfect for:

• GitHub notes
• DSA revision
• OA prep
• Interview prep
• CP practice