Bit Manipulation

Why Bits Matter

Bit manipulation offers O(1) operations that can replace O(n) loops, enables compact state representation, and unlocks elegant solutions to seemingly complex problems. Analogy: Think of a row of light switches. Each switch is independently on or off—that is a bitmask. Flipping a switch is XOR. Checking if a switch is on is AND. Turning a switch on is OR. Bit manipulation lets you operate on all 32 (or 64) switches simultaneously in a single CPU instruction, which is why it is so fast.

Pattern Recognition Signals:

“XOR” in problem statement → XOR properties
“Subset” problems with n ≤ 20 → Bitmask DP
“Toggle/flip” operations → XOR
“Power of 2” → Bit operations
“All pairs XOR” → Contribution technique

Essential Bit Operations

Basic Operations

// AND: Both bits must be 1
a & b

// OR: At least one bit is 1  
a | b

// XOR: Exactly one bit is 1
a ^ b

// NOT: Flip all bits
~a

// Left shift: Multiply by 2^k
a << k  // a * 2^k

// Right shift: Divide by 2^k
a >> k  // a / 2^k

Common Bit Tricks

// Check if i-th bit is set (0-indexed from right)
bool isSet = (n >> i) & 1;

// Set i-th bit
n = n | (1 << i);

// Clear i-th bit
n = n & ~(1 << i);

// Toggle i-th bit
n = n ^ (1 << i);

// Get lowest set bit
int lowbit = n & (-n);

// Clear lowest set bit
n = n & (n - 1);

// Check if n is power of 2
bool isPow2 = n && !(n & (n - 1));

// Count set bits (popcount)
int cnt = __builtin_popcount(n);      // for int
int 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 bit
int pos = 31 - __builtin_clz(n);      // 32-bit
int pos = 63 - __builtin_clzll(n);    // 64-bit

// Check if all bits in range [l, r] are set
bool allSet = ((n >> l) & ((1 << (r - l + 1)) - 1)) == ((1 << (r - l + 1)) - 1);

XOR Properties

XOR is one of the most powerful tools in CP. Understanding its properties deeply is essential for problems rated 1400+. Why XOR is special: Unlike AND and OR, XOR is invertible (you can “undo” it) and self-inverse (applying it twice gives back the original). This makes it perfect for toggling, cancellation, and finding unique elements.

// XOR properties -- memorize these, they appear constantly
a ^ 0 = a          // Identity: XOR with 0 changes nothing
a ^ a = 0          // Self-inverse: any number cancels itself
a ^ b = b ^ a      // Commutative: order does not matter
(a ^ b) ^ c = a ^ (b ^ c)  // Associative: grouping does not matter

// Consequence: if a ^ b = c, then:
a ^ c = b           // XOR both sides with a: a^a^b = a^c => b = a^c
b ^ c = a           // Similarly
// This is why XOR can "recover" a missing value

Application: Find Single Element

// All elements appear twice except one
int findSingle(vector<int>& arr) {
    int result = 0;
    for (int x : arr) {
        result ^= x;
    }
    return result;
}

Application: Find Two Missing Numbers

// Array should have 1 to n, but two numbers are missing
pair<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};
}

Pattern 1: Bitmask DP (Subsets)

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 i Transition: For each unvisited city j:

dp[mask | (1<<j)][j] = \min(dp[mask][i] + dist[i][j])

// Traveling Salesman Problem
int 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;
}

Pattern 2: Iterate Over Subsets

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)

sub = 1010 → (1010-1) & 1010 = 1001 & 1010 = 1000
sub = 1000 → (1000-1) & 1010 = 0111 & 1010 = 0010
sub = 0010 → (0010-1) & 1010 = 0001 & 1010 = 0000
sub = 0000 → stop

Subsets: {1,3}, {3}, {1}, {} ✓

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

// Iterate over all subsets of mask
for (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 masks
for (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)

Sum Over Subsets (SOS DP)

Compute sum of all subsets for each mask. The Problem: For each mask, compute

\sum_{sub \subseteq mask} a[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:

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

// dp[mask] = sum of a[sub] for all sub ⊆ mask
vector<int> a(1 << n);  // Input
vector<int> dp = a;     // Copy

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)];
        }
    }
}

Pattern 3: XOR Basis

Find basis vectors for XOR space. The Concept: Any set of numbers can be represented by a “basis”—a minimal set where:

Every number in the original set can be formed by XORing some basis elements
No basis element can be formed by XORing others

Analogy to Linear Algebra: Just like vectors in linear algebra, but with XOR instead of addition! Key Properties:

Basis size ≤ 60 (for 64-bit numbers, at most one element per bit position)
Maximum XOR = XOR all basis elements with leading bit 1, then greedily add others
Count of distinct XORs = 2^(basis size)

How insertion works:

For each basis element, try to eliminate its leading bit from x
If x becomes 0, it was already representable → don’t add
If x ≠ 0, add it to basis (it brings new information)

Example: Inserting

Insert 3 (0b011): basis empty → basis = [3]
Insert 5 (0b101): 5 XOR 3 = 6 ≠ 0 → basis = [5, 3] (sorted by leading bit)
Insert 6 (0b110): 6 XOR 5 = 3 → 3 XOR 3 = 0 → don't add (6 = 5 XOR 3)

Basis = {5, 3}, all XORs: 0, 3, 5, 6 (2^2 = 4 values)

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(); }
};

Pattern 4: Contribution Technique

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
- Number of pairs with different bit b: cnt0 × cnt1
- Contribution to total: cnt0 × cnt1 × 2^b

Example: arr = [1, 2, 3] = [01, 10, 11]

Bit 0: cnt1 = 2 (numbers 1, 3), cnt0 = 1 (number 2)
       Contribution = 1 × 2 × 1 = 2

Bit 1: cnt1 = 2 (numbers 2, 3), cnt0 = 1 (number 1)
       Contribution = 1 × 2 × 2 = 4

Total = 6

Verification: (1⊕2)+(1⊕3)+(2⊕3) = 3+2+1 = 6 ✓

// Sum of XOR of all pairs
long 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 All Subarray XORs

// XOR of XOR of all subarrays
int 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;
}

Pattern 5: Bitmask Operations on Sets

// Check if set A is subset of B
bool isSubset = (A & B) == A;

// Check if sets are disjoint
bool disjoint = (A & B) == 0;

// Union of sets
int unionAB = A | B;

// Intersection
int 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 set
int size = __builtin_popcount(A);

Pattern 6: Gray Code

Generate sequence where consecutive elements differ by exactly 1 bit. Why Gray code matters in CP: Some problems require visiting all 2^n subsets such that each step adds or removes exactly one element. This is exactly what Gray code provides. It also appears in problems about Hamiltonian paths on hypercubes. How n ^ (n >> 1) works: For any binary number, this formula flips exactly one bit compared to the previous number’s Gray code. The proof relies on the observation that incrementing n in binary flips a contiguous block of bits, and XOR with the right-shifted version “collapses” that block into a single bit flip. Worked example: n = 3 (8 codes)

i=0: 000 ^ 000 = 000  (0)
i=1: 001 ^ 000 = 001  (1) -- 1 bit changed
i=2: 010 ^ 001 = 011  (3) -- 1 bit changed
i=3: 011 ^ 001 = 010  (2) -- 1 bit changed
i=4: 100 ^ 010 = 110  (6) -- 1 bit changed
i=5: 101 ^ 010 = 111  (7) -- 1 bit changed
i=6: 110 ^ 011 = 101  (5) -- 1 bit changed
i=7: 111 ^ 011 = 100  (4) -- 1 bit changed

// Convert binary to Gray code: one XOR operation
int binaryToGray(int n) {
    return n ^ (n >> 1);
}

// Convert Gray code back to binary
int grayToBinary(int g) {
    int n = 0;
    for (; g; g >>= 1) {
        n ^= g;  // Accumulate XOR of all higher bits
    }
    return n;
}

// Generate all 2^n Gray codes
vector<int> grayCode(int n) {
    vector<int> result;
    for (int i = 0; i < (1 << n); i++) {
        result.push_back(binaryToGray(i));
    }
    return result;
}

Pattern 7: Meet in the Middle with Bitmask

For n up to 40, split into two halves.

// Subset sum with n up to 40
bool 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;
}

Common Mistakes

Mistake 1: Integer overflow in shifts

// WRONG - 1 is int, overflow for i >= 31
1 << i

// CORRECT
1LL << i

Mistake 2: Operator precedence

// WRONG - & has lower precedence than ==
if (n & (1 << i) == 1)

// CORRECT
if ((n & (1 << i)) != 0)
// or
if (n >> i & 1)

Mistake 3: Signed right shift Right shift of negative numbers is implementation-defined. Use unsigned types when needed.

Practice Problems

Beginner (1000-1300)

Problem	Pattern	Link
Bit Strings	Counting	CSES
Gray Code	Gray code	CSES

Intermediate (1300-1600)

Problem	Pattern	Link
Apple Division	Bitmask	CSES
Hamming Distance	XOR + popcount	CSES
Xor Maximization	XOR basis	CF 895C

Advanced (1600-1900)

Problem	Pattern	Link
Elevator Rides	Bitmask DP	CSES
SOS DP	Sum over subsets	CF 165E

Key Takeaways

XOR is Powerful

Self-inverse, associative, and perfect for finding duplicates.

Bitmask for Small N

n ≤ 20: enumerate 2^n states directly.

Bit Contribution

Count each bit’s contribution independently.

Meet in Middle

n ≤ 40: split into two halves of 2^20 each.

Next Up

Chapter 20: Contest Strategy

Master the art of competitive programming contests.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Bit Manipulation

Bit Manipulation

Why Bits Matter

Essential Bit Operations

Basic Operations

Common Bit Tricks

XOR Properties

Application: Find Single Element

Application: Find Two Missing Numbers

Pattern 1: Bitmask DP (Subsets)

Pattern 2: Iterate Over Subsets

Sum Over Subsets (SOS DP)

Pattern 3: XOR Basis

Pattern 4: Contribution Technique

XOR of All Subarray XORs

Pattern 5: Bitmask Operations on Sets

Pattern 6: Gray Code

Pattern 7: Meet in the Middle with Bitmask

Common Mistakes

Practice Problems

Beginner (1000-1300)

Intermediate (1300-1600)

Advanced (1600-1900)

Key Takeaways

XOR is Powerful

Bitmask for Small N

Bit Contribution

Meet in Middle

Next Up

Chapter 20: Contest Strategy

​Bit Manipulation

​Why Bits Matter

​Essential Bit Operations

​Basic Operations

​Common Bit Tricks

​XOR Properties

​Application: Find Single Element

​Application: Find Two Missing Numbers

​Pattern 1: Bitmask DP (Subsets)

​Pattern 2: Iterate Over Subsets

​Sum Over Subsets (SOS DP)

​Pattern 3: XOR Basis

​Pattern 4: Contribution Technique

​XOR of All Subarray XORs

​Pattern 5: Bitmask Operations on Sets

​Pattern 6: Gray Code

​Pattern 7: Meet in the Middle with Bitmask

​Common Mistakes

​Practice Problems

​Beginner (1000-1300)

​Intermediate (1300-1600)

​Advanced (1600-1900)

​Key Takeaways

XOR is Powerful

Bitmask for Small N

Bit Contribution

Meet in Middle

​Next Up

Chapter 20: Contest Strategy

Bit Manipulation

Why Bits Matter

Essential Bit Operations

Basic Operations

Common Bit Tricks

XOR Properties

Application: Find Single Element

Application: Find Two Missing Numbers

Pattern 1: Bitmask DP (Subsets)

Pattern 2: Iterate Over Subsets

Sum Over Subsets (SOS DP)

Pattern 3: XOR Basis

Pattern 4: Contribution Technique

XOR of All Subarray XORs

Pattern 5: Bitmask Operations on Sets

Pattern 6: Gray Code

Pattern 7: Meet in the Middle with Bitmask

Common Mistakes

Practice Problems

Beginner (1000-1300)

Intermediate (1300-1600)

Advanced (1600-1900)

Key Takeaways

Next Up