Bitwise Operations & Bitmask

Concept

Bitmask uses an integer's binary representation to encode a set of boolean states. Bit i being 1 means element i is 'selected'. This enables compact subset representation, fast set operations via bitwise operators, and efficient DP over subsets. Essential for problems with n <= 20 where you need to enumerate all 2^n subsets.

When to Use

  • ▸Enumerating all subsets of a set (n <= 20)
  • ▸Bitmask DP — TSP (Traveling Salesman), assignment problems
  • ▸Representing visited states compactly
  • ▸Set operations (union = OR, intersection = AND, toggle = XOR)
  • ▸Checking powers of 2, counting set bits

Intuition

An integer with n bits can represent any subset of {0, 1, ..., n-1}. Bit i is 1 if element i is in the subset. Checking membership: mask & (1 << i). Adding element: mask | (1 << i). Removing: mask & ~(1 << i). Toggling: mask ^ (1 << i). To enumerate all subsets, loop mask from 0 to (1 << n) - 1. For bitmask DP, the state is the set of items already used, and you try adding each unused item.

Complexity

Time
O(2^n * n) for subset enumeration, O(2^n * n^2) for TSP DP
Space
O(2^n) for bitmask DP

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    // --- Bit Manipulation Basics ---
    int x = 13;  // binary: 1101

    // Check if i-th bit is set
    int i = 2;
    if(x & (1 << i)) cout << "bit " << i << " is set\n";

    // Set i-th bit
    x = x | (1 << 1);  // 1101 -> 1111 = 15

    // Clear i-th bit
    x = x & ~(1 << 0);  // 1111 -> 1110 = 14

    // Toggle i-th bit
    x = x ^ (1 << 3);  // 1110 -> 0110 = 6

    // Count set bits
    cout << __builtin_popcount(x) << " bits set\n";

    // Check if power of 2
    // (x & (x-1)) == 0 means power of 2

    // --- Enumerate All Subsets ---
    int n;
    cin >> n;

    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    for(int mask = 0; mask < (1 << n); mask++){
        int sum = 0;
        for(int i = 0; i < n; i++){
            if(mask & (1 << i)){
                sum += v[i];
            }
        }
        // process subset with this sum
    }

    // --- Bitmask DP: Minimum cost to assign n tasks to n people ---
    // dp[mask] = min cost to complete tasks in mask
    // mask represents which tasks are done
    //
    // int n;
    // cin >> n;
    // vector<vector<int>> cost(n, vector<int>(n));
    // for(int i = 0; i < n; i++)
    //     for(int j = 0; j < n; j++)
    //         cin >> cost[i][j];
    //
    // const int inf = 1e9+7;
    // vector<int> dp(1 << n, inf);
    // dp[0] = 0;
    //
    // for(int mask = 0; mask < (1 << n); mask++){
    //     if(dp[mask] == inf) continue;
    //     int person = __builtin_popcount(mask);  // which person to assign next
    //     for(int task = 0; task < n; task++){
    //         if(mask & (1 << task)) continue;  // task already done
    //         int newMask = mask | (1 << task);
    //         dp[newMask] = min(dp[newMask], dp[mask] + cost[person][task]);
    //     }
    // }
    //
    // cout << dp[(1 << n) - 1] << "\n";

    return 0;
}

// Sample Input:
// 4
// 3 1 4 2
//
// (enumerates all 16 subsets and computes their sums)