Bit Manipulation Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

// Every value appears twice except one: pairs cancel (x ^ x = 0, x ^ 0 = x).
int singleOfPairs(const vector<int>& a) {
    int x = 0;
    for (int v : a) x ^= v;
    return x;
}

// Exactly two values appear once: XOR of all = a ^ b, which is non-zero.
// Any 1-bit of it differs between a and b; split the array by that bit.
vector<int> twoSingles(const vector<int>& a) {
    unsigned all = 0;
    for (int v : a) all ^= v;
    unsigned low = all & -all;               // lowest 1-bit (unsigned: safe for INT_MIN)
    int g0 = 0, g1 = 0;
    for (int v : a) ((unsigned)v & low ? g1 : g0) ^= v;   // each pair lands in one group
    return {g0, g1};
}

// Every value appears k times except one: count each bit mod k.
int singleOfK(const vector<int>& a, int k) {
    unsigned res = 0;
    for (int b = 0; b < 32; b++) {
        int cnt = 0;
        for (int v : a) cnt += ((unsigned)v >> b) & 1;
        if (cnt % k) res |= 1u << b;         // 1u: bit 31 must not overflow int
    }
    return (int)res;
}

// n & (n - 1) removes the lowest 1-bit:  1100 -> 1000.
int countOnes(unsigned n) {
    int c = 0;
    while (n) { n &= n - 1; c++; }           // runs once per 1-bit
    return c;
}

// A power of two has exactly one 1-bit. Check n > 0 first (0, negatives, INT_MIN).
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

// x & -x keeps only the lowest 1-bit:  1100 -> 0100.
unsigned lowestBit(unsigned x) { return x & -x; }

// Read, set, clear, flip bit i (0 = rightmost). Use unsigned when i can be 31.
bool getBit(unsigned n, int i) { return (n >> i) & 1; }
unsigned setBit(unsigned n, int i) { return n | (1u << i); }
unsigned clearBit(unsigned n, int i) { return n & ~(1u << i); }
unsigned flipBit(unsigned n, int i) { return n ^ (1u << i); }

// Bits of every number 0..n: i without its last bit is i >> 1, already solved.
vector<int> countBitsUpTo(int n) {
    vector<int> bits(n + 1, 0);
    for (int i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);
    return bits;
}

// Reverse all 32 bits: exactly 32 steps, so leading zeros become trailing zeros.
uint32_t reverse32(uint32_t n) {
    uint32_t r = 0;
    for (int i = 0; i < 32; i++) { r = (r << 1) | (n & 1); n >>= 1; }
    return r;
}

// XOR of a[l..r] in O(1) after O(N) setup: the shared prefix cancels.
struct PrefixXor {
    vector<int> p;                            // p[i] = a[0] ^ ... ^ a[i-1], p[0] = 0
    PrefixXor(const vector<int>& a) : p(a.size() + 1, 0) {
        for (size_t i = 0; i < a.size(); i++) p[i + 1] = p[i] ^ a[i];
    }
    int query(int l, int r) const { return p[r + 1] ^ p[l]; }
};

// AND of every number in [left, right] = their common binary prefix.
// Each lower bit is 0 somewhere in the range, so it becomes 0.
int rangeAnd(int left, int right) {
    int shift = 0;
    while (left != right) { left >>= 1; right >>= 1; shift++; }
    return left << shift;
}

// Largest group with AND > 0: the group must share one bit, so count per bit.
int largestSharingABit(const vector<int>& a) {
    int best = 0;
    for (int b = 0; b < 31; b++) {
        int cnt = 0;
        for (int v : a) cnt += (v >> b) & 1;
        best = max(best, cnt);
    }
    return best;
}

// A mask is a set: bit i = item i is in. n up to ~20.
//   in:  (mask >> i) & 1     add: mask | (1 << i)     size: __builtin_popcount(mask)
void forEachSubset(int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++)
            if ((mask >> i) & 1) { /* item i is in this subset */ }
    }
}

// Visit-all DP (TSP shape): dp[mask][last] = best cost to start at 0,
// visit exactly the items in mask, and stand at last.
int visitAll(const vector<vector<int>>& cost) {
    int n = cost.size(), FULL = (1 << n) - 1;
    const int INF = 1e9;
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;                             // only item 0 visited, standing at 0
    for (int mask = 1; mask <= FULL; mask++)  // smaller masks are always finished first
        for (int last = 0; last < n; last++) {
            if (dp[mask][last] == INF) continue;
            for (int nxt = 0; nxt < n; nxt++) {
                if ((mask >> nxt) & 1) continue;
                int nm = mask | (1 << nxt);
                dp[nm][nxt] = min(dp[nm][nxt], dp[mask][last] + cost[last][nxt]);
            }
        }
    int best = INF;
    for (int last = 0; last < n; last++) best = min(best, dp[FULL][last] + cost[last][0]);
    return n == 1 ? 0 : best;
}

// Every submask of mask (for "split a set into two parts" DPs): 3^n in total.
void forEachSubmask(int mask) {
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) { /* use sub */ }
}