Skip to content

Bits Are Sets

Pillar: Set -- "The integer 13 (binary 1101) IS the set \(\{0, 2, 3\}\). Every bitwise operation is a set operation."

The Setup

You have \(n\) items. You want to track which subset you've selected. You could use a vector<bool>, a set<int>, or a hash set. Or you could use a single integer.

The integer \(13\) in binary is \(1101_2\). Read the bit positions from right to left: bit 0 is on, bit 1 is off, bit 2 is on, bit 3 is on. That's the set \(\{0, 2, 3\}\).

One integer. One register. \(O(1)\) per operation. That's the pitch. But the real payoff isn't speed -- it's that every bitwise operator you already know is a set operator in disguise. Once you see this mapping, bitmask problems stop being about bits and start being about sets.

Binary Representation as a Set

An integer with \(n\) bits represents a subset of \(\{0, 1, \ldots, n-1\}\). Bit \(k\) is 1 if element \(k\) is in the set, 0 otherwise.

Integer Binary Set
\(13\) \(1101_2\) \(\{0, 2, 3\}\)
\(11\) \(1011_2\) \(\{0, 1, 3\}\)
\(7\) \(0111_2\) \(\{0, 1, 2\}\)
\(0\) \(0000_2\) \(\emptyset\)
\(15\) \(1111_2\) \(\{0, 1, 2, 3\}\)

Read this table until it feels automatic. The integer \(7\) isn't "seven" -- it's the set containing elements 0, 1, and 2. The integer \(0\) is the empty set. The integer \(2^n - 1\) is the full universe.

Bitwise Operations Are Set Operations

This is the core insight. Every bitwise operator has a set-theoretic name.

AND = Intersection

\(13 \mathbin{\&} 11 = 9\)

In sets: \(\{0, 2, 3\} \cap \{0, 1, 3\} = \{0, 3\}\)

Binary: \(1101 \mathbin{\&} 1011 = 1001 = 9\). The bits that survive are exactly the elements in both sets.

OR = Union

\(13 \mathbin{|} 11 = 15\)

In sets: \(\{0, 2, 3\} \cup \{0, 1, 3\} = \{0, 1, 2, 3\}\)

Binary: \(1101 \mathbin{|} 1011 = 1111 = 15\). A bit is on if it appears in either set.

XOR = Symmetric Difference

\(13 \oplus 11 = 6\)

In sets: \(\{0, 2, 3\} \mathbin{\triangle} \{0, 1, 3\} = \{1, 2\}\)

Binary: \(1101 \oplus 1011 = 0110 = 6\). A bit is on if it appears in exactly one of the two sets, not both. Remember this one -- it comes back in Ch8 when we study Nim. The Sprague-Grundy XOR combines game states precisely because XOR is symmetric difference.

NOT = Complement

\(\mathord{\sim}13 = \ldots 110010_2\) (inverts all bits)

In practice you want complement within a universe of \(n\) bits: \(((1 \ll n) - 1) \oplus 13\) gives \(\{0, 1, \ldots, n-1\} \setminus \{0, 2, 3\}\).

For \(n = 4\): \(15 \oplus 13 = 2 = \{1\}\). That's \(\{0,1,2,3\} \setminus \{0,2,3\}\).

The Shape Observation: OR Grows, AND Shrinks

Take any sequence of integers \(a_1, a_2, \ldots, a_k\) and compute the running OR. Each new OR can only turn bits ON, never off. The set can only grow.

\[a_1 \mathbin{|} a_2 \mathbin{|} \cdots \mathbin{|} a_k\]

Since a 32-bit integer has at most 30 useful bits, the running OR can change at most 30 times across the entire sequence. After that, it's stuck.

Now do the same with AND. Each new AND can only turn bits OFF. The set can only shrink. At most 30 changes.

This is a Shape observation: OR is monotonically non-decreasing (as a set), AND is monotonically non-increasing.

OR Can Only Grow — The Subarray Bound

Take any starting position in an array and compute the OR as you extend rightward:

  • OR of \(A[3..3] = A[3]\)
  • OR of \(A[3..4] = A[3] \mathbin{|} A[4]\)
  • OR of \(A[3..5] = A[3] \mathbin{|} A[4] \mathbin{|} A[5]\)
  • ...

Each step, the OR either stays the same or gets bigger. It never shrinks. Because OR only sets bits — it never clears them. Once a bit is on, it stays on.

And since a number has at most \(\log_2(V)\) bits (where \(V\) is the maximum value), the OR can change at most \(\log_2(V)\) times before every bit is set and it stops growing.

This means: from any fixed starting position, there are at most \(\log_2(V)\) distinct OR values as you extend the subarray. Even though there are \(O(N)\) possible ending positions, the number of distinct results is tiny.

Across all starting positions, that gives \(O(N \log V)\) distinct subarray OR values total. Way less than the \(O(N^2)\) subarrays. This bound shows up in many problems involving range OR queries and is the key to solving them efficiently.

Submask Enumeration

Given a bitmask \(\text{mask}\), how do you iterate over all subsets of the set it represents?

The classic loop:

for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
    // submask is a non-empty subset of mask
}

Trace it for \(\text{mask} = 13 = \{0, 2, 3\}\):

Step submask (binary) submask (set)
1 \(1101\) \(\{0, 2, 3\}\)
2 \(1100\) \(\{2, 3\}\)
3 \(1001\) \(\{0, 3\}\)
4 \(1000\) \(\{3\}\)
5 \(0101\) \(\{0, 2\}\)
6 \(0100\) \(\{2\}\)
7 \(0001\) \(\{0\}\)

Seven submasks, which is \(2^3 - 1\) (the mask has 3 set bits, and we skip the empty set).

Why does (submask - 1) & mask work? Subtracting 1 flips the lowest set bit and sets all lower bits. The & mask clears any bits that aren't in the original mask, jumping directly to the next valid submask. No wasted iterations.

Why \(O(3^n)\) Over All Masks

If you enumerate submasks for every mask from \(0\) to \(2^n - 1\):

for (int mask = 0; mask < (1 << numElements); mask++) {
    for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
        // process (mask, submask) pair
    }
}

The total work is \(O(3^n)\), not \(O(4^n)\). Why? Each element has exactly 3 states relative to a (mask, submask) pair: (1) not in mask, (2) in mask but not in submask, (3) in both mask and submask. With \(n\) elements and 3 choices each, there are \(3^n\) total pairs.

For \(n = 20\), that's \(3^{20} \approx 3.5 \times 10^9\) -- tight but feasible with simple inner work. For \(n = 15\), \(3^{15} \approx 14\) million -- comfortable.

Bitmask DP: Why It Exists

Bitmask DP uses integers as DP indices because integers ARE sets. The transition mask | (1 << j) is set union — adding element \(j\). The test mask & (1 << j) is set membership. The full treatment of bitmask DP — states, transitions, TSP walkthrough — belongs to the DP course. The point here: if \(N \le 20\) and the problem needs to track which elements you've chosen (not just how many), bitmask DP is the tool.

Common Bit Manipulation Patterns

These are the building blocks. Know them cold.

Check if bit \(k\) is set:

\[(\texttt{n} \gg k) \mathbin{\&} 1\]

Shift element \(k\) to position 0, then mask everything else.

Set bit \(k\) (add element \(k\)):

\[\texttt{n} \mathbin{|} (1 \ll k)\]

Union with the singleton \(\{k\}\).

Clear bit \(k\) (remove element \(k\)):

\[\texttt{n} \mathbin{\&} \mathord{\sim}(1 \ll k)\]

Intersect with the complement of \(\{k\}\).

Toggle bit \(k\) (symmetric difference with \(\{k\}\)):

\[\texttt{n} \oplus (1 \ll k)\]

If \(k\) was in the set, remove it. If it wasn't, add it.

Lowest set bit (smallest element):

\[\texttt{n} \mathbin{\&} (-\texttt{n})\]

Two's complement trick. \(-n\) flips all bits and adds 1, so \(n \mathbin{\&} (-n)\) isolates the lowest 1-bit. This is how Fenwick trees navigate their index structure.

Count set bits (set cardinality):

__builtin_popcount(n) in C++. Counts the number of elements in the set.

Iterate all set bits:

while (mask) {
    int lowestBit = mask & (-mask);
    int bitPosition = __builtin_ctz(mask);
    mask ^= lowestBit;
}

Extract the lowest set bit, record its position, then remove it via XOR (symmetric difference with a singleton). Runs in \(O(\text{popcount})\) -- you only visit elements that are actually in the set.

Code

Three utilities: converting integers to sets, enumerating submasks, and a complete bitmask brute force for the Apple Division problem (partition \(n\) elements into two groups minimizing the weight difference).

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

void printAsSet(int mask) {
    cout << "{";
    bool first = true;
    for (int bit = 0; bit < 30; bit++) {
        if ((mask >> bit) & 1) {
            if (!first) cout << ", ";
            cout << bit;
            first = false;
        }
    }
    cout << "}\n";
}

void enumerateSubmasks(int mask) {
    for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
        printAsSet(submask);
    }
}

int main() {
    int numElements;
    cin >> numElements;
    vector<long long> weight(numElements);
    long long totalWeight = 0;
    for (int i = 0; i < numElements; i++) {
        cin >> weight[i];
        totalWeight += weight[i];
    }
    long long bestDifference = totalWeight;
    for (int mask = 0; mask < (1 << numElements); mask++) {
        long long groupWeight = 0;
        for (int bit = 0; bit < numElements; bit++) {
            if ((mask >> bit) & 1) groupWeight += weight[bit];
        }
        long long difference = abs(totalWeight - 2 * groupWeight);
        bestDifference = min(bestDifference, difference);
    }
    cout << bestDifference << "\n";
    return 0;
}

Complexity: \(O(2^n \cdot n)\) time, \(O(n)\) space. Feasible for \(n \le 20\).

Common Mistakes

  • Forgetting 1LL << k for \(k \ge 31\). 1 << 31 is undefined behavior in C++ because 1 is a 32-bit int. Use 1LL << k whenever \(k\) might reach 31 or higher.
  • Off-by-one in submask loop. The loop for (int submask = mask; submask > 0; ...) skips the empty set. If you need the empty set too, handle it separately after the loop.
  • Using ~mask without bounding. ~mask flips all 32 (or 64) bits, not just the \(n\) you care about. For complement within \(n\) bits, use ((1 << n) - 1) ^ mask.
  • Initializing TSP DP with the wrong base case. The base is \(\text{dp}[1][0] = 0\), not \(\text{dp}[0][0] = 0\). City 0 starts already visited, so mask \(= 1\), not mask \(= 0\).

Quick Recap

  • An integer IS a set. Bit \(k\) on means element \(k\) is in the set.
  • AND = intersection, OR = union, XOR = symmetric difference, NOT = complement. XOR returns in Ch8 (Nim) and Ch11 (subset convolution).
  • OR only grows, AND only shrinks -- at most \(O(\log V)\) changes across a sequence. This is a Shape property you'll exploit in segment trees.
  • Submask enumeration runs in \(O(2^{\text{popcount}})\) per mask, \(O(3^n)\) total over all masks.
  • Every bitmask DP is a set DP. The state is which elements you've chosen, the transitions are set operations.
  • TSP bitmask DP: state \(\text{dp}[\text{mask}][\text{lastCity}]\), transition via OR to add a city, \(O(2^N \cdot N^2)\) total. The loop order over masks automatically respects subset dependencies.
  • Reach for bitmask DP when \(N \le 20\), you need to track which elements (not how many), and order within the set doesn't matter.

Problems

Problem Link Difficulty Technique
LC 78 -- Subsets leetcode.com/problems/subsets Medium Bitmask enumeration of all \(2^n\) subsets
CSES -- Apple Division cses.fi/problemset/task/1623 Easy Bitmask brute force, minimize partition difference
LC 2044 -- Count Maximum Bitwise-OR Subsets leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets Medium Enumerate subsets, track running OR
CSES -- Hamiltonian Flights cses.fi/problemset/task/1690 Hard Bitmask DP, count Hamiltonian paths
LC 943 -- Shortest Superstring leetcode.com/problems/find-the-shortest-superstring Hard Bitmask DP similar to TSP, minimize overlap