Bitmasking is one of the most powerful and elegant techniques in competitive programming. It allows us to represent subsets using bits and perform complete search efficiently.
Complete Search → Iterative Approach
We can iterate over all subsets of a set of size n using integers from 0 to (1 << n) - 1.
Each bit in the number represents whether we include the element or not.
Difference Between Terms
| Term | Meaning | Order Matters? |
|---|---|---|
| Subarray | Continuous part of an array | Yes |
| Subset | Any combination of elements | No |
| Subsequence | Elements in order, not necessarily contiguous | Yes |
Example
Suppose we have the array:
[1, 2, 5, 9]
Each bitmask from 0000 to 1111 (binary) represents a subset:
| Mask (binary) | Decimal | Subset Example |
|---|---|---|
| 0000 | 0 | {} |
| 0001 | 1 | {9} |
| 0010 | 2 | {5} |
| 0011 | 3 | {5, 9} |
| 0100 | 4 | {2} |
| 0101 | 5 | {2, 9} |
| 0110 | 6 | {2, 5} |
| 0111 | 7 | {2, 5, 9} |
| 1000 | 8 | {1} |
| 1111 | 15 | {1, 2, 5, 9} |
1 << n = (2^n) → total number of subsets.
Example 1: Count Subsequences with Sum = K
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int &x : a) cin >> x;
int res = 0;
for (int mask = 0; mask < (1 << n); ++mask) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (mask >> i & 1) {
sum += a[i];
}
}
if (sum == k) ++res;
}
cout << res;
We loop through all 2^n masks and check which subsets have a sum equal to k.
Example 2: Apple Division (CSES Problem)
Find the minimum difference between the total weights of two groups of apples.
int n;
cin >> n;
vector<int> a(n);
for (auto &i : a) cin >> i;
int mn = INT_MAX;
for (int mask = 0; mask < (1 << n); ++mask) {
int g1 = 0, g2 = 0;
for (int i = 0; i < n; i++) {
if (mask >> i & 1) g1 += a[i];
else g2 += a[i];
}
mn = min(mn, abs(g1 - g2));
}
cout << mn;
Bitset
A bitset is an array of bits (0 or 1). It is more memory-efficient and provides useful built-in functions.
#include <bitset>
bitset<62> b;
Useful Methods
| Function | Description |
|---|---|
b.count() | Returns number of 1s |
b.to_string() | Converts to a string of 0s and 1s |
b.set() | Sets all bits to 1 |
b.reset() | Sets all bits to 0 |
b.all() | True if all bits = 1 |
b.any() | True if any bit = 1 |
b.none() | True if all bits = 0 |
b.to_ullong() | Converts to unsigned long long |
Example
bitset<8> a = 5; // 00000101
bitset<8> b = 9; // 00001001
bitset<8> c = a | b; // bitwise OR
cout << c << "\n"; // 00001101
cout << a[2] << "\n"; // access bit #2
a = ~a; // bitwise NOT
Complexity
- Operations on a 64-bit bitset → O(64)
- Operations on a 32-bit bitset → O(32)
Summary
- Use bitmasking to represent subsets efficiently.
- Iterate from
0to(1 << n) - 1for complete search. - Use
bitsetwhen you need fast operations on bits. - Common use cases: subset sum, partitioning, combinatorial search.



