> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Bit Manipulation

> Master bitwise operations, bitmasks, and XOR tricks for competitive programming

# 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.

<Note>
  **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
</Note>

***

## Essential Bit Operations

### Basic Operations

```cpp theme={null}
// 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

```cpp theme={null}
// 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.

```cpp theme={null}
// 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

```cpp theme={null}
// 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

```cpp theme={null}
// 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 {A, B, C, D}:

* mask = 0b1010 = 10 means subset {B, D} (bits 1 and 3 are set)
* mask = 0b1111 = 15 means all elements {A, B, C, D}
* 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])$

```cpp theme={null}
// 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

```cpp theme={null}
// 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
```

```cpp theme={null}
// 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**:

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

**Example**: Inserting {3, 5, 6}

```
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)
```

```cpp theme={null}
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 ✓
```

```cpp theme={null}
// 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

```cpp theme={null}
// 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

```cpp theme={null}
// 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
```

```cpp theme={null}
// 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.

```cpp theme={null}
// 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

<Warning>
  **Mistake 1: Integer overflow in shifts**

  ```cpp theme={null}
  // WRONG - 1 is int, overflow for i >= 31
  1 << i

  // CORRECT
  1LL << i
  ```
</Warning>

<Warning>
  **Mistake 2: Operator precedence**

  ```cpp theme={null}
  // WRONG - & has lower precedence than ==
  if (n & (1 << i) == 1)

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

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

***

## Practice Problems

### Beginner (1000-1300)

| Problem     | Pattern   | Link                                         |
| ----------- | --------- | -------------------------------------------- |
| Bit Strings | Counting  | [CSES](https://cses.fi/problemset/task/1617) |
| Gray Code   | Gray code | [CSES](https://cses.fi/problemset/task/2205) |

### Intermediate (1300-1600)

| Problem          | Pattern        | Link                                                       |
| ---------------- | -------------- | ---------------------------------------------------------- |
| Apple Division   | Bitmask        | [CSES](https://cses.fi/problemset/task/1623)               |
| Hamming Distance | XOR + popcount | [CSES](https://cses.fi/problemset/task/2136)               |
| Xor Maximization | XOR basis      | [CF 895C](https://codeforces.com/problemset/problem/895/C) |

### Advanced (1600-1900)

| Problem        | Pattern          | Link                                                       |
| -------------- | ---------------- | ---------------------------------------------------------- |
| Elevator Rides | Bitmask DP       | [CSES](https://cses.fi/problemset/task/1653)               |
| SOS DP         | Sum over subsets | [CF 165E](https://codeforces.com/problemset/problem/165/E) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="XOR is Powerful" icon="wand-magic-sparkles">
    Self-inverse, associative, and perfect for finding duplicates.
  </Card>

  <Card title="Bitmask for Small N" icon="chess-board">
    n ≤ 20: enumerate 2^n states directly.
  </Card>

  <Card title="Bit Contribution" icon="calculator">
    Count each bit's contribution independently.
  </Card>

  <Card title="Meet in Middle" icon="arrows-left-right-to-line">
    n ≤ 40: split into two halves of 2^20 each.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 20: Contest Strategy" icon="arrow-right" href="/courses/competitive-programming/20-contest-strategy">
  Master the art of competitive programming contests.
</Card>