Bit manipulation offers O(1) operations that can replace O(n) loops, enables compact state representation, and unlocks elegant solutions to seemingly complex problems.
// AND: Both bits must be 1a & b// OR: At least one bit is 1 a | b// XOR: Exactly one bit is 1a ^ b// NOT: Flip all bits~a// Left shift: Multiply by 2^ka << k // a * 2^k// Right shift: Divide by 2^ka >> k // a / 2^k
// Check if i-th bit is set (0-indexed from right)bool isSet = (n >> i) & 1;// Set i-th bitn = n | (1 << i);// Clear i-th bitn = n & ~(1 << i);// Toggle i-th bitn = n ^ (1 << i);// Get lowest set bitint lowbit = n & (-n);// Clear lowest set bitn = n & (n - 1);// Check if n is power of 2bool isPow2 = n && !(n & (n - 1));// Count set bits (popcount)int cnt = __builtin_popcount(n); // for intint cnt = __builtin_popcountll(n); // for long long// Find position of lowest set bit (0-indexed)int pos = __builtin_ctz(n); // count trailing zeros// Find position of highest set bitint pos = 31 - __builtin_clz(n); // 32-bitint pos = 63 - __builtin_clzll(n); // 64-bit// Check if all bits in range [l, r] are setbool allSet = ((n >> l) & ((1 << (r - l + 1)) - 1)) == ((1 << (r - l + 1)) - 1);
// XOR propertiesa ^ 0 = a // Identitya ^ a = 0 // Self-inversea ^ b = b ^ a // Commutative(a ^ b) ^ c = a ^ (b ^ c) // Associative// If a ^ b = c, then:a ^ c = bb ^ c = a
// Array should have 1 to n, but two numbers are missingpair<int, int> findTwoMissing(vector<int>& arr, int n) { int xorAll = 0; for (int x : arr) xorAll ^= x; for (int i = 1; i <= n; i++) xorAll ^= i; // xorAll = a ^ b where a, b are missing int diffBit = xorAll & (-xorAll); // Lowest different bit int group1 = 0, group2 = 0; for (int x : arr) { if (x & diffBit) group1 ^= x; else group2 ^= x; } for (int i = 1; i <= n; i++) { if (i & diffBit) group1 ^= i; else group2 ^= i; } return {group1, group2};}
When n ≤ 20, enumerate all 2^n subsets using bitmask.The Idea: Represent a subset as a binary number. If bit i is set, element i is in the subset.Example: For n=4 elements :
mask = 0b1010 = 10 means subset (bits 1 and 3 are set)
mask = 0b1111 = 15 means all elements
mask = 0b0000 = 0 means empty set
Common State Design: dp[mask][last] where:
mask = which elements have been used/visited
last = the last element used (for problems where order matters)
Traveling Salesman Problem (TSP)Find the shortest route visiting all n cities exactly once and returning to start.State: dp[mask][i] = minimum cost to visit cities in mask, ending at city iTransition: For each unvisited city j:
dp[mask∣(1<<j)][j]=min(dp[mask][i]+dist[i][j])
Copy
// Traveling Salesman Problemint tsp(int n, vector<vector<int>>& dist) { const int INF = 1e9; // dp[mask][i] = min cost to visit cities in mask, ending at i vector<vector<int>> dp(1 << n, vector<int>(n, INF)); dp[1][0] = 0; // Start at city 0 for (int mask = 1; mask < (1 << n); mask++) { for (int u = 0; u < n; u++) { if (!(mask & (1 << u))) continue; if (dp[mask][u] == INF) continue; for (int v = 0; v < n; v++) { if (mask & (1 << v)) continue; int newMask = mask | (1 << v); dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]); } } } int ans = INF; for (int i = 0; i < n; i++) { ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]); } return ans;}
Iterating all subsets of a mask: The trick sub = (sub - 1) & mask generates all subsets in decreasing order.Why it works: Subtracting 1 flips the rightmost 1 and all bits after it. ANDing with mask keeps only valid positions.Example: mask = 0b1010 (bits 1 and 3)
Complexity of iterating all submasks of all masks: O(3^n), not O(4^n)!
Each element is either: not in mask, in mask but not in sub, or in both
3 choices per element → 3^n total iterations
Copy
// Iterate over all subsets of maskfor (int sub = mask; sub > 0; sub = (sub - 1) & mask) { // Process subset 'sub'}// Don't forget empty set if needed// Process empty set separately// Iterate over all submasks of all masksfor (int mask = 0; mask < (1 << n); mask++) { for (int sub = mask; ; sub = (sub - 1) & mask) { // Process if (sub == 0) break; }}// Total complexity: O(3^n)
Compute sum of all subsets for each mask.The Problem: For each mask, compute ∑sub⊆maska[sub]. Naive: O(3^n). SOS DP: O(n · 2^n).The Insight: Process one bit at a time. After processing bit i, dp[mask] contains the sum over all subsets that may differ from mask only in bits 0 to i.Visual for n=3:
Copy
Initial: dp[mask] = a[mask]Process bit 0: dp[mask] += dp[mask with bit 0 flipped off] (if bit 0 is on) dp[001] += dp[000], dp[011] += dp[010], etc.Process bit 1: dp[mask] += dp[mask with bit 1 flipped off] (if bit 1 is on) dp[010] += dp[000], dp[011] += dp[001], etc.Process bit 2: similar...Result: dp[mask] = sum of a[sub] for all sub ⊆ mask
Copy
// dp[mask] = sum of a[sub] for all sub ⊆ maskvector<int> a(1 << n); // Inputvector<int> dp = a; // Copyfor (int i = 0; i < n; i++) { for (int mask = 0; mask < (1 << n); mask++) { if (mask & (1 << i)) { dp[mask] += dp[mask ^ (1 << i)]; } }}
class XORBasis {public: vector<long long> basis; void insert(long long x) { for (long long b : basis) { x = min(x, x ^ b); } if (x) { basis.push_back(x); // Keep sorted for finding min/max for (int i = basis.size() - 1; i > 0 && basis[i] > basis[i-1]; i--) { swap(basis[i], basis[i-1]); } } } long long getMax() { long long result = 0; for (long long b : basis) { result = max(result, result ^ b); } return result; } bool canRepresent(long long x) { for (long long b : basis) { x = min(x, x ^ b); } return x == 0; } int size() { return basis.size(); }};
Count total XOR sum across all pairs/subsets.The Insight: Instead of iterating over all pairs/subsets (expensive), consider each bit independently and count its contribution.For XOR: A bit contributes to the XOR of a pair only if the two numbers have different values at that bit.Sum of XOR of all pairs:
For each bit position b:
Count numbers with bit b = 1: call it cnt1
Count numbers with bit b = 0: call it cnt0 = n - cnt1
// Sum of XOR of all pairslong long sumPairXOR(vector<int>& arr) { int n = arr.size(); long long total = 0; for (int bit = 0; bit < 30; bit++) { int count1 = 0; // Numbers with this bit set for (int x : arr) { if (x & (1 << bit)) count1++; } int count0 = n - count1; // Pairs with different bit values contribute 2^bit total += (long long)count0 * count1 * (1 << bit); } return total;}
// XOR of XOR of all subarraysint xorOfSubarrayXors(vector<int>& arr) { int n = arr.size(); int result = 0; for (int i = 0; i < n; i++) { // arr[i] appears in how many subarrays? // As starting point: n - i choices for end // As middle/end: i + 1 choices for start // Total: (i + 1) * (n - i) subarrays contain arr[i] long long count = (long long)(i + 1) * (n - i); if (count % 2 == 1) { result ^= arr[i]; } } return result;}
// Check if set A is subset of Bbool isSubset = (A & B) == A;// Check if sets are disjointbool disjoint = (A & B) == 0;// Union of setsint unionAB = A | B;// Intersectionint intersect = A & B;// Symmetric difference (in A or B but not both)int symDiff = A ^ B;// A minus B (in A but not B)int diff = A & ~B;// Size of setint size = __builtin_popcount(A);
// Subset sum with n up to 40bool subsetSum(vector<int>& arr, long long target) { int n = arr.size(); int half = n / 2; // Generate all sums for first half set<long long> firstHalf; for (int mask = 0; mask < (1 << half); mask++) { long long sum = 0; for (int i = 0; i < half; i++) { if (mask & (1 << i)) sum += arr[i]; } firstHalf.insert(sum); } // Check second half for (int mask = 0; mask < (1 << (n - half)); mask++) { long long sum = 0; for (int i = 0; i < n - half; i++) { if (mask & (1 << i)) sum += arr[half + i]; } if (firstHalf.count(target - sum)) return true; } return false;}