Bitmasks & Bit Operations¶

In one sentence

When there are at most about \(20\) yes/no choices, write each choice as one bit of an integer: counting state from \(0\) to \(2^n - 1\) then visits every possible combination exactly once.

1. What problem does it solve?¶

Example — 1097B · Petr and a Combination Lock (4-quick_power · C, rating 1200)

A lock has a pointer on a 360° dial that starts at \(0\). You must make exactly \(n\) rotations of \(a_1, \dots, a_n\) degrees, in this order, each one either clockwise or counter-clockwise. Is there a choice of directions that brings the pointer back to \(0\)?

Limits: \(n \le 15\), \(a_i \le 180\).

Input      Output
3
10
20
30         YES

3
10
10
10         NO

3
120
120
120        YES

Each rotation is a yes/no choice ("clockwise?"), so there are \(2^n\) plans. With \(n \le 15\) that is \(32\,768\) plans, each checked in \(15\) steps: about half a million steps. Trying everything is fast enough; the only question is how to list all \(2^n\) plans without writing \(15\) nested loops.

2. The math¶

2.1 An integer is a row of switches¶

Write a number in binary. Bit \(i\) (counting from the right, starting at \(0\)) is worth \(2^i\).

state = 5  =  1 0 1   (binary)
              | | └─ bit 0 = 1  → rotation 0 clockwise
              | └─── bit 1 = 0  → rotation 1 counter-clockwise
              └───── bit 2 = 1  → rotation 2 clockwise

Every plan for \(n\) rotations is a row of \(n\) switches, and every row of \(n\) switches is exactly one integer from \(0\) (all off) to \(2^n - 1\) (all on). So the loop

for (int state = 0; state < (1 << n); state++)

visits all plans, each exactly once.

2.2 Reading and changing one bit¶

Want	Code	Example with `x = 13 = 1101₂`, `k = 1`
is bit \(k\) on?	`x >> k & 1` or `x & (1 << k)`	`13 >> 1 = 110₂ = 6`, `6 & 1 = 0` → off
turn bit \(k\) on	`x \| (1 << k)`	`1101 \| 0010 = 1111` = 15
flip bit \(k\)	`x ^ (1 << k)`	`1101 ^ 0010 = 1111` = 15
turn bit \(k\) off	`x & ~(1 << k)`	`1101 & 1101 = 1101` = 13 (already off)
\(2^k\)	`1 << k`	`1 << 3 = 8`

2.3 Trace on sample 1¶

\(a = (10, 20, 30)\), bit \(i\) on means "add \(a_i\)", off means "subtract \(a_i\)".

state	bits (2 1 0)	sum	\(\equiv 0 \pmod{360}\)?
0	0 0 0	\(-10-20-30 = -60\)	no
1	0 0 1	\(+10-20-30 = -40\)	no
2	0 1 0	\(-10+20-30 = -20\)	no
3	0 1 1	\(+10+20-30 = 0\)	yes

State \(3\) works, so the answer is YES without looking at states \(4 \dots 7\).

2.4 Cost¶

\(2^n\) states times \(n\) bits each: \(O(n \cdot 2^n)\). From the complexity table, this is fine up to \(n \approx 20\).

3. Lesson notes (8 and 22 March)¶

We often encounter problems with a very small data scale. For example, if we have a maximum of 20 items, we can choose either to take each one or not. This gives us up to \(2^{20}\) different combinations (since for each item, taking it or not taking it corresponds to two options). It's easy to see that \(2^{20}\) is not a particularly large number. If checking each state doesn't consume much time, we can write a very brute-force enumeration: try every single possibility, and we will always arrive at the desired answer (whether there is a solution, no solution, or the maximum/minimum value).

A relatively simple implementation approach is to use binary enumeration (often called bitmasking). We use the \(i\)-th binary bit to indicate whether the \(i\)-th item is selected (1) or not selected (0). As a result, the maximum state is a binary number consisting of \(n\) 1s, and the minimum state is a binary number consisting of \(n\) 0s. Their values are strictly less than \(2^n\), which is equivalent to 1 << n.

Therefore, we can write our enumeration code like this. This is very common in USACO Bronze division problems (enumerating over small data scales).

for(int state=0;state<(1<<n);state++) {
    // current state
    for(int i=0;i<n;i++) {
      if(state>>i&1) { // Or we can write state & (1<<i)
        // the i-th digit is 1
      } else {
        // the i-th digit is 0
      }
    }
}

Additionally, for problems with an exceptionally large data scale, we should first try to manually calculate a few more steps on scratch paper—at least 10. Alternatively, we can write a simulation program ourselves, run it within a certain range according to the problem's requirements, and then observe whether there is a pattern in the output data and whether the actual range of \(n\) can be significantly reduced using modulo operations.

4. Worked solution — Petr and a Combination Lock¶

This is the 8 March enumeration loop with the problem's check inside.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int state = 0; state < (1 << n); state++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (state >> i & 1) {
                sum += a[i];   // bit i on: clockwise
            } else {
                sum -= a[i];   // bit i off: counter-clockwise
            }
        }
        if (sum % 360 == 0) {
            cout << "YES\n";
            return;
        }
    }

    cout << "NO\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

sum can be negative. In C++, -360 % 360 is 0, so the check still works; but -20 % 360 is -20, not 340. If you need the actual position on the dial, use ((sum % 360) + 360) % 360.

5. When to think "bitmask"¶

Sign in the statement	Example
\(n \le 15\), \(n \le 20\) and each item is in or out	choose a subset of items
each position is one of two letters	USACO 2026 · Moo Hunt (`M` or `O`, \(N \le 20\))
amounts are powers of two	USACO 2026 · Purchasing Milk (binary decomposition)

6. Common mistakes¶

state >> i & 1 versus state >> (i & 1)

>> binds tighter than &, so state >> i & 1 means (state >> i) & 1, which is what we want. When unsure, add brackets.

1 << n with \(n \ge 31\)

1 is a 32-bit int. For large shifts write 1LL << n, although at that size enumeration is far too slow anyway.

x & 1 << k == 0

== binds tighter than &, so this is x & ((1 << k) == 0). Write (x >> k & 1) == 0.

7. Practice¶

Problem	Set	Rating	Idea
1097B · Petr and a Combination Lock	4-quick_power · C	1200	\(2^n\) direction plans (this page)
USACO 2026 Contest 2 · Moo Hunt	homework 22 Mar	Bronze	one bit per position, score every board
USACO 2026 Contest 2 · Purchasing Milk	lesson 22 Mar	Bronze	fix prices, then binary decomposition

Credits & licenses

§3 joins the 8 March recap (enumeration) and the Concepts part of the 22 March lesson (shifts, AND, OR, XOR), unchanged apart from heading levels.
Example, bit diagrams, operator table, trace, worked solution and mistakes are ours.